Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

Computational complexity is a part of theoretical computer science that answers questions about how efficient an algorithm is:

  • How much time (as a function of the size of the input) does the algorithm take to produce its output?
  • How much space (such as computer memory) does it require?
  • How much of some other resource does it consume? (For example, this can be the size of a logic circuit solving the problem, or the number of bits of randomness used by a probabilistic algorithm.)

We can similarly ask about the computational complexity of any algorithm that solves a given problem.

Often, very specific details of these answers (such as constant factors or additive terms) depend on specific details such as the computer you're using. To help deal with this, we often stick to determining the asymptotic complexity of an algorithm: see for more details.

A major problem in computational complexity is the P versus NP problem, which asks if a certain class of problems can be solved by an algorithm that runs in a number of steps that's a polynomial function of the input size.

3433 questions
2
votes
0 answers

How can we make Cook-Levin Reduction an implicit log space reduction

This is an exercise mentioned in lots of places. I have searched around for detailed answers, but none of them has explained clearly on a critical part of analysis. Setting: we have an oblivious Deterministic Turing Machine $M$ with 1 input tape, 1…
user84731
  • 29
2
votes
0 answers

reducing #P-complete problem to NP problem

What would be the consequence and meaning of existence of polynomial reduction of #P-complete problem into NP problem (not NP-complete problem)?
user35558
  • 21
2
votes
2 answers

NP-completeness and NP problems

Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not in NP-complete? Or would this just shows the…
Zat Mack
  • 63
2
votes
1 answer

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 $$ of the rest of the data, the following n-fold integer programming problem…
user284639
  • 523
2
votes
2 answers

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 counter example, but this looks a bit sloppy to me..
maggie
  • 21
2
votes
1 answer

Counting number of loops

How many multiplications are performed when the following code fragment is executed? Express your answers in terms of $n$, where $n \geq 10$. for(i = 1; i < n; i = i + 2) for(j= 0; j <= i; j++) a[i][j] = a[i][j]*0.001; Would anyone be…
Xian
  • 89
2
votes
1 answer

Is $(n!)^n$ complexity just said to be $O(n!)$ complexity?

I know that $n!$ complexity is higher than exponential complexity and big-O notation says always use the highest growing $n$ term for the naming. But, seeing as this is a factorial to the power of $n$ rather than $n!+x^n$, does that make a…
user3129805
  • 61
2
votes
1 answer

Prove that $co-RP \subseteq RP^{RP}$

This appears in solutions to an exercise I had: Question: Prove that $RP^{RP}=RP$, or show that it is equivalent to an open question. Answer: $RP^{RP}=RP$ is equivalent to the open question $RP=co-RP$. If $RP=co-RP$, then $RP=RP \cap co−RP=ZPP$,…
Cauthon
  • 389
  • 3
  • 16
2
votes
0 answers

Is there a "C vs NC"-problem, where C stands for "constant time"?

Appologies if this question is utterly naive. I know very little about complexity classes, but like to learn more. Consider the following problem. Given input $n$ (a natural number) we want to find the term $p_1$ in the sequence given by $$p_n =…
Vincent
  • 10,614
2
votes
2 answers

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?
Albert
  • 145
2
votes
0 answers

Why isn't NP=coNP?

My understanding is that if a problem is in NP, there is a nondeterministic polynomial-time Turing machine that decides it. That is to say, if an NP problem has a solution, the NP machine has a poly-length computational path on its computation tree…
user1299784
  • 2,009
2
votes
0 answers

Shouldn't big oh definition be if and if only if, not just if?

This is from Discrete Mathematics and its Applications Shouldn't the if in that definition be an if and only if? Say we know that $n^2$ is in O($n^2$). Then from one side of the if and only if, we know that there are constants c and $n_0$, in this…
committedandroider
  • 1,884
2
votes
1 answer

Computational complexity comparison between MINLP and MILP

Can someone please explain the computational complexity of MINLP and MILP, though both are NP-Hard. What is the advantage of having an MILP formulation over MINLP formulation for a same optimization problem? I have an MINLP problem of 32 binary…
Dipankar Narayanan
  • 39
2
votes
1 answer

Oracles for TQBF

I've seen this question somewhere and I've been thinking about it a lot but couldnt think of an answer. Say you have oracles A and B for the TQFB (True Quantified Boolean Formula) decision problem, one being correct and the other one wrong, but you…
Antonia Anderson
  • 21
1
vote
1 answer

How can I prove that $P \neq EXP$

It seems like $P\neq EXP$ is much easier than $P \neq NP$. How can I prove $P \neq EXP$? (Well, after all I want to know any proof technique of proving there does not exist any algorithm of certain time complexity to prove a decision problem.) It…
Henry
  • 3,125
1 2 3
…
22 23