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)

0
votes
1answer
68 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
60 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
44 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
219 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
5k 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
350 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
214 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
335 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
172 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
94 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
210 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 ...
7
votes
1answer
947 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
515 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
81 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)}$
1
vote
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
1k 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
225 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
2k 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
65 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
329 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
119 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
357 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
248 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
889 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
288 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
224 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
552 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
697 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
78 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
159 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 ...
8
votes
1answer
3k 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
282 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
208 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
103 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
1k 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
241 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 ...
6
votes
0answers
581 views

The Average Running Time Of Euclid Algorithm?

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$? It seems very hard to deduce from the recurrence $T(m,n) = T(n, m ...
2
votes
1answer
363 views

what is the relationship between the complexity class E(and EXP) and NP?

I want to know any relationship between the complexity class E(and EXP) and NP. I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
0
votes
1answer
587 views

What's the big $O$ for this summation?

What would the big $O$ (worst-case runtime complexity; I think it's big $O$?) be for an algorithm that takes this long? I generalized the run time with the summation and put it in wolfram alpha. ...
10
votes
2answers
832 views

How hard is it to do arithmetic?

People in computing are often observed saying that a computation takes $\operatorname{O}(n^3\log n)$ steps or that it's NP-hard or that it's not computable, or that it's primitive recursive, etc. I ...
2
votes
0answers
272 views

Complexity of finding solutions for a system of polynomial equations

Problem A: Given a set of polynomial equations $ f_1=0,\ldots,f_m=0 $, where the $ f_i $'s are multivariate polynomials with $ n $ variables over a field $\mathbb F$, decide whether there is a ...
6
votes
2answers
742 views

Optimization Puzzle

You are given a large number of LEGO blocks of size 1. You can build blocks of other sizes using smaller blocks. For example, you can build a block of size 2 using two of size 1 blocks and then build ...
2
votes
0answers
73 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
5
votes
2answers
1k views

Why is integer factorization considered to be in NP if a quantum computer can compute a factorization in polynomial time?

Sorry if this seems off topic, the cstheory guys told me it was off topic over there, and sent me here. Shor's algorithm on a quantum computer can solve an integer factorization problem in polynomial ...
0
votes
1answer
129 views

Determining computational complexity of stochastic processes

I have an program which implements a Markov chain Monte Carlo process on a system of N bits, stopping when the process converges. Let's use T to denote the average number of steps made by the Markov ...
5
votes
1answer
474 views

how can i prove that square root of n is space constructible

I know that square-root of n is space-constructible. I can't prove it by the space-constructible definition. How can I show that only $\sqrt{n}$ space is used?
3
votes
0answers
202 views

Amortized Analysis for (2,5)-Tree

I need some help with the following problem Definition: A (2,5)-tree is an external search tree, where all leaves have the same depth. Each inner node in a (2,5)-tree has at least 2, and at most 5 ...