Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

1
vote
1answer
38 views

Algorithmic efficiency of rotating a point

I am trying to calculate the algorithmic effciency (Big-O) of rotating n 3-D vertices using the rotation matrix: $\begin{bmatrix}1 & 0 & 0 \\0 & cos(a) & -sin(a) \\ 0 & sin(a) &...
1
vote
1answer
35 views

How do we decide a problem is in NP, but not in P or NPC?

As I understand, NPC set contains only the problems which can be polynomially converted into each other and which are hardest in NP set/ But how do we decide which problems are in NPC and which ...
0
votes
0answers
45 views

nocomputable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
4
votes
1answer
186 views

Giving tight asymptotic bounds for $T(n)=T(\frac{n}{\log n}) + \log\log n$

I don't like coming here for such matters, but this is a homework problem from my Analysis of algorithms class. I've come along the Akra-Bazzi method and different variations on the matter , read ...
0
votes
1answer
52 views

not any computable function f such that x is not in the Halting Problem iff f ( x ) belongs to set of Kolmogorov-random strings

taking clue from this question set of Kolmogorov-random strings is co-re the paper mentioned in the above link talks about the non existence of a computable function how can I show that there is ...
5
votes
1answer
64 views

Is there a number $n$, such that there are $22$ groups of order $n$?

Denot : $N(n)$ : the number of groupfs of order $n$ ? Is there a number $n$ with $N(n)=22$ ? Checking the first about $2000$ numbers, I noticed that there is no $n\in [1,2000]$ with $N(n)=22$. ...
0
votes
0answers
19 views

How to devise an efficient algorithm to detect if every cycle of a weighted graph has, at least, two edges with the maximum weight

Let M be an adjacency matrix representing a weighted graph G. I'm trying to devise an algorithm to verify if, for every cicle C of G, the edge with biggest weight of C is not unique on C. I can think ...
3
votes
0answers
41 views

Is the problem : Determine the number of groups with order $n$ NP-hard?

It can be hard to determine the number of groups with order $n$, especially for $n=2^k$. So, I wonder, whether there is a polynomial algorithm doing this. I think, this is not the case because for ...
0
votes
1answer
20 views

How to start dealing with this recurrence relation

I have never seen a recurrence in this form, so I don't know how to proceed. I'm supposed to find asymptotic bounds (preferably $\Theta$(something)) for: $$T(n) =T\bigg(\frac{n}{\log n}\bigg)+ \log \...
1
vote
1answer
59 views

Time Complexity of Sorting Algorithm

Here's my question: Analyze the runtime of the following algorithm. Will it successfully sort array S of n elements with values from 0 to m-1? ...
2
votes
1answer
84 views

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings?...
0
votes
0answers
19 views

Computational Complexity of exponentiating

I'm currently studying this paper and I am trying to understand the complexity of the interpolate algorithm, which is supposed to be $O((l+m)^2)$. So first the algorithm runs in $r$ steps where $r\...
0
votes
1answer
25 views

The approximability of different NP-hard problems

I'm fairly new to the topic Computational Complexity and had the following question (I therefore apologies before hand for any poorly stated terminology). Suppose i have two optimization problems $A$...
0
votes
1answer
26 views

Asymptotic complexity of power of logs

I'm trying to simplify $\Theta(lg^k(n/2))$. I believe it's $\Theta(lg^kn)$ but i don't know if the following proof is correct... i'd love to receive some input I tried doing - $$\Theta(lg^k(n/2))=\...
0
votes
0answers
14 views

Np-hardness of a problem related to the knapsack problem

I am trying to know whether the following problem is NP-hard: Input: A positive number k and N pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
3
votes
1answer
46 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? $$f:\mathbb{N}\...
0
votes
0answers
18 views

$NP^A \neq coNP^A$(Baker, Gill and Solovay theorem)

From Baker, Gill and Solovay theorem we know that there is an oracle $A$ such that $NP^A \neq coNP^A$ Now what can we conclude from this if $A \in P$ or $A \in NP$ ? And correct me if I'm wrong, if ...
0
votes
1answer
61 views

What does $\forall X: A^X \subseteq B^X$ mean?

In Greg Kuperberg's complexity zoology inclusion diagram, there is a color coding based on whether or not $$ \forall X : A^X \subseteq B^X $$ is proven, disproven, or unknown. What does this ...
1
vote
0answers
18 views

A Complexity Problem of Cliques

I've been trying to figure out the Karp Reduction $$CLIQUE(G,k) \preceq IND(G,k),$$ Where $CLIQUE(G,k)$ is the decision problem "Is there a clique of size at least $k$ in the graph $G$" and $IND(G,k)$...
0
votes
1answer
29 views

Does storage scheme matter in multiplication of two matrices? [closed]

Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity ...
1
vote
1answer
31 views

Zero-One Optimization

I have looked through some resources with varying success. Perhaps someone can provide a place to start. Suppose we have a finite set of real numbers, $A$, and a partition, $A=\displaystyle\bigcup_{i=...
0
votes
1answer
45 views

Complete trail - walk traversing each vertex at least once, each edge at most once

I would like to know the status of the following problem: Given a simple graph, is there a walk traversing each vertex at least once and each edge at most once? (I am asking for a complete trail, a ...
1
vote
1answer
29 views

Changing variable in summation

I'm trying to understand the analysis of Quick Select algorithm that I found on StackOverflow: http://stackoverflow.com/a/25796762/3356218 Case 1 of proof: I understand it but the first transition, ...
1
vote
1answer
13 views

Binary enconding length

What does binary-encoding length means? For instance if my theorem says "An algorithm solves in time which is polynomial in n and in the binary-encoding length $<l,u,b,w>$ of the rest of the ...
2
votes
2answers
21 views

Complexity notation (Omega) consequence

In my algorithms class, the professor told us that the following holds: $$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$ But is this always true ? I couldn't come up with a ...
0
votes
1answer
29 views

What the proof, instance, and verifier mean in the definition of NP problem?

I came across a definition of NP problems: Definition. A decision problem $X ∈ NP$, if there exists a polynomial time verifier $V$ such that For every yes instance $x ∈ X$, there exists a ...
1
vote
0answers
41 views

Understanding AI through a complexity function

I've been trying to understand in light of a few apparent paradoxes for me. It appears reasonable that we could prove any mathematical problem that has a well defined answer can be solved by a ...
0
votes
0answers
22 views

Does 'polynomial' (or 'exponential') running time for 3-SAT problem refer to the number of variables or the number of clauses?

This sounds like an incredibly stupid question but none of the relevant Wikipedia pages seem to answer it. So... if the runtime of an algorithm to solve 3SAT has running time $O(f(n))$ for some ...
1
vote
0answers
23 views

Akra-Bazzi method - constructive proof

As I was familiarizing myself with different methods of computing complexities of recurrences, I stumbled upon the Akra-Bazzi method. Seeing such a beautiful result literally made my day. I was able ...
1
vote
1answer
47 views

equivalence of theory of reals and Rationals

Present a sentence φ that is in theory of reals but not in thoery of Rationals Following up from this question what is the approach to show that both the theories are equivalent Th(R, 0, 1, +, ≤) ...
-2
votes
1answer
60 views

P vs NP, finding algorithms in polynomial time?

Concerning an NP problem, such as the travelling salesmen problem. Say for a graph with N nodes there exists an algorithm $A(N)$ which can solve the problem in time $N^3$ (for example). But.... to ...
0
votes
1answer
46 views

Statistical distance and test

Here is a bit of context and definitions: Let $\mathcal D$ and $\mathcal E$ be distributions of probability over a finite set $A$ and $X, Y$ be random variables following $\mathcal D$ and $\...
1
vote
1answer
42 views

How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.
1
vote
1answer
18 views

Convex hull from cloud of co-ordinates

I'm trying to design an algorithm to find the convex hull of a set of co-ordinates using the slope between two points to determine if a point is part of the convex hull. I'm testing a set of five ...
0
votes
0answers
21 views

Pspace Complete Problem

image1 image2 In theory of computation text book I was going through this problem ... I have added the images What I wanted to know is that in the middle of the problem it is given that "Using this ...
0
votes
1answer
26 views

Big O - Recurrence

I am given a function as follows: ...
0
votes
0answers
29 views

Complexity theory : Lower Bound for the Theory of Real Addition

In theory of computation text book I came across this page ... I have added the images I wanted to know what at the bottom of the page it is given that However,we can combine these into one ...
0
votes
0answers
112 views

Cover of vertices - NP Algorithm analysis, correctness and execution time

Introduction Given a graph $G = (V, E)$, we call a set $T \subseteq V$ a cover if any edge $e \in E$ has one extremity in T. Decision Problem: Given $G = (V, E)$ with n nodes and a $k \le n$, return ...
0
votes
0answers
9 views

lower bound Tutte polynomial for planar graphs

The Tutte Polynomial $T(G, x, y)$ s a #P-Hard problem except for the hyperbola (x-1)(y-1)=1 and some other specific points. For the case of planar graphs, Dell $\textit{et. al.}$ mention (in the ...
0
votes
1answer
184 views

How we decide for a given context free grammar generate an infinite number of strings?

Consider the following decision problems: (P1) Does a given finite state machine accept a given string? (P2) Does a given context free grammar generate an infinite number of strings? Which of the ...
0
votes
1answer
21 views

Getting big Oh from summation

Merging two sorted arrays $A_1$ and $A_2$ with $n_1$ and $n_2$ elements, respectively, takes $O(n_1+n_2)$ time. This strategy begins by merging two arrays of size $n$ to create an array of size $2n$. ...
0
votes
1answer
22 views

Need help in understanding proof “approach” and meaning for “1st order Theory of dense linear orders w/o endpoints is PSPACE complete”

So in my class we are giving a proof for 1st order Theory of dense linear orders w/o endpoints is PSPACE complete. The proof that it is in PSPACE is basically to reduce TQBF. Let $\phi = \exists ...
1
vote
0answers
11 views

Comparing the orders of complexity.

I do have to evaluate a property defined as $$w = \sqrt{\det\left(\textbf{J}\,\textbf{J}^\text{T}\right)} = \prod_{i = 1}^n \sigma_i,$$ where $\textbf{J} \in R^{3 x n}$ and $n>3$. Using the ...
0
votes
0answers
40 views

Hilbert 10th, bounded arithmetic, NP=co-NP

I keep seeing claims that if Hilbert 10th, if can be proved in bounded arithmetic (specifically $T_{2}$), then it will automatically mean that NP=co-NP. Unfortunately, none of these claims provide any ...
1
vote
4answers
1k views

Newton form vs. Lagrange form for interpolating polynomials

I'm just wondering, what are the advantages of using either the Newton form of polynomial interpolation or the Lagrange form over the other? It seems to me, that the computational cost of the two are ...
0
votes
0answers
31 views

Size of input relate to numbers of operations. Is it exponential?

Let assume that size of input is: $$ O( \log b + \log n) $$ and amount of operations on input is: $$O(b\log^2n)$$ Is amount of operations exponential relate to size of input? My intuition is: yes ...
0
votes
1answer
31 views

time complexity [closed]

Given n integers a1,a2..an and some integer S. To test whether there exists xi belongs to {0,1} such that: ...
1
vote
5answers
63 views

What's “computer's method” in calculating beta for a regression line

Since this is not from a problem set but just something I've been thinking, please forgive me for possible (wording) errors. Consider a set of data points $(x_n,b_n)$. We would like to know the ...
0
votes
1answer
34 views

Hardest boolean formula circuit complexity upper bound

I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$. So far ...
0
votes
0answers
39 views

Proof of NP-completeness in the strong sense

I am just learning about the $\textbf{NP}$-completeness in the strong sense. I know that the $3$-partition problem: A set $X$ of $3n$ positive integers and a positive integer $B$ is given where each ...