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)

3
votes
1answer
75 views

A card game with a long path

I recently played an online card game in which the cards were spread on the table. The goal was for me to pick up as many as possible, subject to the following rule: After picking up the first card, ...
2
votes
1answer
101 views

A question about sorting

I've always been thought that the fastest way to sort an array of numbers has complexity $O(n \log (n))$. However, radix sort has complexity $O(kn)$ where $k$ is the number of bits. There are even ...
3
votes
1answer
110 views

Determining position at some point in time

I try to solve the following problem. On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, ...
0
votes
1answer
110 views

What is the time complexity of determining coefficients of generating functions?

My question is inspired by the following problem: Given $k$ coins with denominations $\{c_1, ..., c_k\}$, how many ways are there to generate $n$ cents? This can be solved in $\Theta(nk)$ time using ...
1
vote
0answers
55 views

existence of $DLOGTIME$-complete problems

Just curious - is there any problem that can be considered as $DLOGTIME$-complete? Or if not, has it been proven that there does not exist a complete class? (By being complete, I mean that it has ...
1
vote
1answer
39 views

RE problems that are neither RE-complete nor recursive

As stated, is there any decision problems in the complexity class RE that are neither RE-complete nor recursive? It seems that almost all of nonrecursive RE problems are in RE-complete...
0
votes
1answer
58 views

Do the complete areas of various complexity classes have infinitely many problems? [duplicate]

Possible Duplicate: Complexity classes and number of problems I know that almost all of complexity classes that have some significance have infinite number of decision problems. Then what ...
1
vote
2answers
85 views

non-complete problem collapsing to a lower complexity class complete problem

Let us say that there is a NP problem that is not a complete problem. And let us assume that someone found that the problem is in fact P-complete problem. Does this imply P=NP?
0
votes
1answer
22 views

size of first-order formulae to express a property

Let $FO-SIZE[s(n)]$ be the set of properties expressible by uniform sequences of first- order formulas, $\{\phi_{i}\}_{i\in \mathbb{Z^+}}$ , such that the $n$th formula has $O(s(n))$ symbols and ...
2
votes
1answer
442 views

Form or asymptotic behaviour of $T(n) =2T(n-1)+n$ [duplicate]

$T(n) =$ if $n=1$, then time execution is $1$, if $n \geq 2$ then $2T(n-1)+n$ The options are: $T(n) = 2^{n+1} - n - 2$ $T(n) = O(n2^n)$ $T(n) = \Omega(n)$ $T(n) = \theta(2^n)$ Thanks.
2
votes
1answer
91 views

LFP - shortest path problem

Curious question: Can anyone show me how to describe shortest path problem using LFP + first order logic? I am just getting lost on how to describe the problem, though I know that LFP + first-order ...
0
votes
1answer
69 views

Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?

A algorithm require one second to resolve a problem of size $1000$ a local machine. How long time take the same algorithm to resolve the same problem for a problem size of $10.000$ if the algorithm ...
1
vote
1answer
1k views

Big-O notation always holds for this two functions?

For two any functions $f(n)$ and $g(n)$ always holds: $f(n) = O(g(n))$ or $g(n) = O(f(n))$ Right? Thanks
1
vote
1answer
62 views

Descriptive Complexity Theory - operator, structure and iteration?

In descriptive complexity theory, FO is the set of properties (problem) expressible by first-order logic. I get this part, but what are all these transitive operators and some structures? From ...
1
vote
1answer
46 views

Complexity class that is the set of languages expressible by first-order logic

PH is the complexity class that is the set of languages expressible by second-order logic. If so, is there any complexity class that is the set of languages expressible by first-order logic? It seems ...
0
votes
2answers
63 views

Complexity classes and number of problems

Will every complexity class contain infinite number of problems? If they do not, do common complexity classes (e.g. P,NP,PSPACE,EXPTIME,EXPSPACE etc.) contain infinite number of problems?
1
vote
1answer
234 views

example of complexity class that does not have complete problems

Many known complexity classes have complete problems; however, according to what I heard, not all complexity classes have complete problems. So, what are some examples of the complexity classes that ...
3
votes
2answers
6k views

how do you prove that 3-SAT is NP-complete?

As it is, how do you prove that 3-SAT is NP-complete? I know what it means by NP-complete, so I do not need an explanation on that. What I want to know is how do you know that one problem, such as ...
1
vote
0answers
408 views

Polynomial-Time reduction: Clique Problem

Here is an exercise my friend proposed to me: Show that the maximum clique problem polynomial time reduces to the maximum independent set problem. Here is my attempt at solving it: It is known ...
2
votes
1answer
227 views

Using Polynomial-Time Reduction to Prove Hardness

From what I understand of polynomial-time reduction, there are two instances of it: many-one and Turing. Many-one simply breaks down problem A into many instances of problem B, and uses the (known) ...
6
votes
1answer
397 views

What are the prerequisites in order to pursue the P vs. NP problem?

I'm a math major at Berkeley, and am focusing or logics/fundamentals, in particulars groups. I was just trying to see if I were to, for personal interest, get a better understand and perhaps try ...
1
vote
4answers
176 views

A “State Hierarchy” Theorem for Turing Machines?

In complexity theory, there are time hierarchy theorems for Turing machines that show that for certain functions $f$, there exist problems that cannot be solved by a Turing machine in $o(f(n))$ time. ...
1
vote
2answers
95 views

Simplifying a logarithm of a little-o (circuit complexity)

I have an expression which I think is $o(2^n)$, but I'm having difficulty simplifying it: $o(2^n/n)\log(o(2^n/n) + n)$ I can ignore the extra $n$ sitting at the end, since $o(2^n/n) + n = o(2^n/n + ...
0
votes
3answers
238 views

role of constant of proportionality in complexity of algorithm

what is the role of the constant of proportionality while comparing the the order of complexities of two competing algorithms. Like in case ALGO A has complexity 3*O(n) while ALGO B has complexity ...
8
votes
1answer
1k views

Divisor summatory function for squares

The Divisor summatory function is a function that is a sum over the divisor function. $$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor ...
3
votes
1answer
575 views

Long integer multiplication using FFT in integer rings

I would like to perform long integer (~= polynomial) multiplication using the FFT or its direct analogue, but never leave integer rings. Please excuse in advance all my mistakes in formulation and ...
1
vote
1answer
84 views

Finding the computational complexity of an algorithm

Algorithm: for (int i = 0; i < 2*n; i += 2) for (int j = n; j >i; j--) foo(); I want to find the number of times foo() is called. ...
-1
votes
1answer
72 views

$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$

I must use O notation to show that: $T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$ But, I don't understand what mean: $n^{O(1)}$
2
votes
2answers
2k views

Is $2^{2n} = O(2^n)$?

Is $2^{2n} = O(2^n)$? My solution is: $2^n 2^n \leq C_{1}2^n$ $2^n \leq C_{1}$, TRUE. Is this correct?
2
votes
2answers
2k views

Connecting all points on a plane with shortest path possible

I want to connect N nodes, so all are connected, by connecting each node to their closest neighbors. An image of what I'm looking for is below. Currently I solve it like this: I add a random node to ...
1
vote
1answer
238 views

average distance in a graph

Having a graph of $n$ vertices in Euclidean $m$-dimensional space, is it possible to find average (Euclidean) distance between the vertices in $O(n)$ steps? Is there a deterministic algorithm for ...
2
votes
3answers
3k views

Help proving that $(n+a)^b = \Theta(n^b)$

Please you apologize me by my English. I don't know how make that: $$(n+a)^b = \Theta(n^b), b > 0$$ I know, I must to find two constants such that: $$ c_{1} n^b \leq (n+a)^b \leq c_{2} n^b $$ I ...
0
votes
2answers
66 views

Complexity class P - is $k$ only natural numbers?

I think I have seen an algorithm that has $x^{1.5}$ as its complexity. However, according to Wikipedia, it states that the complexity class P is defined as $\bigcup_{k\in\mathbb{N}} ...
0
votes
1answer
367 views

symmetric difference of languages - both are in NP and coNP

I have this problem, Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like: $L_1 \oplus L_2 = \{x | x$ is in exactly one of ...
3
votes
2answers
124 views

Is it possible to prove that a problem $P$ is decidable in $O(\phi)$ without providing an algorithm that decides $P$ in $O(\phi)$?

Phrased another way: Are there any problems that are known to be decidable in a better worst-case time complexity than the best known procedure?
2
votes
2answers
384 views

the set of sentences (i.e. closed formulas) of first-order logic and the Chomsky hierarchy

The set of well-formed formulas (wffs) in first-order logic (FOL) is decidable, because it's straightforward to translate the standard recursive syntax rules into a context free grammar, and all ...
0
votes
1answer
252 views

Time complexity of algorithm computing averages

I am new, and wanted to see if someone can help me. What is the running time of your algorithm (below) with respect to the variable $n$? Give an upper bound of the form ${\cal O}(f(n))$ and a ...
0
votes
1answer
1k views

What is the computational complexity of a brute force perfect numbers finder algorithm?

A loop goes thru all numbers from one to N to find perfect numbers. For each number in the range, it checks all numbers less than it to see if it's a divisor by modding it by the number and checking ...
2
votes
2answers
319 views

Knapsack with non-trivial “utility” function

The standard knapsack problem imagines a thief trying to stick the most items in his knapsack as possible. It assumes that having, say, two Picasso paintings is twice as good as having one. We might ...
2
votes
0answers
228 views

2-Player Game PSpace-Completeness

So there is a n x n game board and each location on the board has an integer. Player one picks a number from row 1 and player 2 picks a number from row 2 and they alternate until there are no more ...
0
votes
1answer
600 views

NP-Completeness of Certain Bounded Degree Graphs

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) L = set of all (G, k) where G is a graph with ...
1
vote
2answers
724 views

P or NP-Complete? (concerning 2-CNF formulas)

I have two languages that I want to either prove is in P or NP-complete. 1) 2-CNF formulas where there exists an assignment that satisfies the 3/4 of the first 1000 clauses and all of the rest. 2) ...
0
votes
1answer
82 views

How do I estimate the time taken? (Growth Rates)

Suppose you have a program that solves an AI problem. When the problem size is $N = 1,000$ your program takes 10 seconds to find a solution. Estimate the time it will take to solve a problem of size ...
4
votes
1answer
171 views

Connect 4 - SAT

My question is about how the Hasbro game Connect4 can be viewed as a SAT problem. My initial guess is that it would actually be QSAT, and that the 'problem' would be something along the lines of: "Is ...
9
votes
1answer
4k views

Complexity of counting the number of triangles of a graph

The trivial approach of counting the number of triangles in a simple graph $G$ of order $n$ is to check for every triple $(x,y,z) \in {V(G)\choose 3}$ if $x,y,z$ forms a triangle. This procedure ...
3
votes
1answer
306 views

Proving NP-completeness intuition

When approaching a problem in NP, initially not knowing whether the problem is in P or NP-complete (or some other choice). It seems to me the only way one can go about "solving" this problem is to ...
4
votes
0answers
222 views

Proving NP-completeness (hardness) exercises

I am looking for a list of exercises that can be done to practice polynomial time reductions to prove NP-hardness of problems. I know there are hundreds (thousands?) of problems proven to be NP-hard. ...
3
votes
1answer
104 views

Treatments of Mahaney's Theorem?

Could you direct me to some readable treatments of Mahaney's theorem? The best thing I've been able to find is Fortnow's lecture. I'm especially interested in discussion around the theorem and its ...
4
votes
2answers
2k views

what is the computational complexity of solving a quadratic program with linear inequality constraints

I'm aware of several solution methods and have several solvers at my disposal, but I can't for the life of me find analysis on the complexity. In particular, I'm interested in the complexity of ...
4
votes
1answer
258 views

if P=NP, then is E=NE?

If the computational complexity class P equals to NP, does the complexity class E equal to the class NE? E is defined as $DTIME(O(2^{O(n)}))$ NE is defined as $NTIME(O(2^{O(n)}))$ Thank you very ...