MathOverflow Stack Exchange
MathOverflow Stack Exchange

Questions tagged [computational-complexity]

This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; context-free languages; applications of complexity theory to finite model theory, logic and discrete mathematics.

For those who want to ask about Kolmogorov Complexity, it is recommended that you also look for tag "information theory". Usually this tag also relates with combinatorics and logic.

Please distinguish this tag from those algorithm-specific problems that are asked on Stack Overflow, Computer Science or Theoretical Computer Science, the major concern of this category of questions should be more on the design-side instead of the implementation side.

1299 questions
30
votes
1 answer

Why is proving P != NP so hard?

Does anyone have any insight into why it is so hard to prove that P != NP conjecture? There seems to be so much evidence in its favor, and so many problems and techniques with which to attack it, that I don't get why it has remained unproven for so…
k2forever
  • 381
29
votes
2 answers

A combination of two well-known complexity problems

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other doesn't. Can you tell in polynomial time which…
gowers
  • 28,729
27
votes
4 answers

How do we know that P != LINSPACE without knowing if one is a subset of the other?

I've seen that P != LINSPACE (by which I mean SPACE(n)), but that we don't know if one is a subset of the other. I assume that means that the proof must not involve showing a problem that's in one class but not the other, so how else would you go…
wjomlex
  • 503
27
votes
2 answers

Is there a syntactic characterization for BPP, BQP, or QMA?

Background The complexity classes BPP, BQP, and QMA are defined semantically. Let me try to explain a little bit what is the difference between a semantic definition and a syntactic one. The complexity class P is usually defined as the class of…
Kaveh
  • 5,362
26
votes
6 answers

Are there any interesting examples of random NP-complete problems?

Here's an example of the kind of thing I mean. Let's consider a random instance of 3-SAT, where you choose enough clauses for the formula to be almost certainly unsatisfiable, but not too many more than that. So now you have a smallish random…
gowers
  • 28,729
24
votes
5 answers

Are there complexity classes with provably no complete problems?

A problem is said to be complete for a complexity class $\mathcal{C}$ if a) it is in $\mathcal{C}$ and b) every problem in $\mathcal{C}$ is log-space reducible to it. There are natural examples of NP-complete problems (SAT), P-complete problems…
Akhil Mathew
  • 25,291
18
votes
2 answers

Is #k-XORSAT #P-complete?

k-XORSAT is the problem of deciding whether a Boolean formula $$\bigwedge_{i \in I} \oplus_{j=1}^k l_{s_{ij}}$$ is satisfiable. Here $\oplus$ denotes the binary XOR operation, $I$ is some index set, and each clause has $k$ distinct literals…
András Salamon
  • 2,330
15
votes
3 answers

Is this strange problem NP-complete?

The following quadratic expression can be simplified: (x+1)(x+2) + (x+1)(x-3) + 2x(2x-1) - (3x+1)(x-3) - 2x(x+2). What is the easiest way of doing the simplification? (It would be good to think about this for a few seconds before continuing.) A…
gowers
  • 28,729
14
votes
3 answers

Complexity of computing matrix rank over integers

Does computing the rank of an integer matrix have complexity polynomial in the size of the input? The Gaussian elimination algorithm is polynomial in the number of elementary operations (addition and multiplication), but the intermediate size of of…
user1855
  • 471
14
votes
2 answers

Correct to characterise NP set as P-time image of P set?

[I'm not familiar with the terminology, so when I write P (resp. NP) set, I mean a subset of the integers whose membership function is a decision problem in P (resp. NP).] Is it correct to say that a set is NP if and only if it is the image of a P…
Tom Ellis
  • 2,775
13
votes
2 answers

Can more polynomial time compensate for less polynomial memory?

I'm wondering what is known about the relation between time and memory for polynomial-time algorithms (which are necessarily also polynomial-space). In particular, I would like to learn what is known about less time vs. less memory, in the following…
Franka Waaldijk
  • 1,606
12
votes
2 answers

NP not equal to SPACE(n)

Exercise 3.2 of Computational Complexity, a Modern Approach states: Prove: NP != SPACE(n) [Hint: we don't know if either is a subset of the other.] I don't know how to solve this problem. It's in the diagonalization chapter. I've looked around…
LowerBounds
  • 643
11
votes
1 answer

Descriptive complexity theoretic-characterizations of P and NP

Prompted by Vinay Deolalikar's purported proof of P != NP, I've been reading up on Descriptive Complexity for some background material. The major successes of Descriptive Complexity include Fagin's result that $NP=SO\exists$ (that is, the class NP…
Henry Yuen
  • 1,909
11
votes
1 answer

Does EXP $\in$ P/poly imply NP=RP?

I guess the answer is that this unknown. Maybe this implies some "lowness" result on NP relative to BPP?
Sebastian Ben Daniel
  • 243
10
votes
2 answers

How many Complexity Classes do you know?

We can read about the main complexity classes in textbooks and online in Wikipedia: http://en.wikipedia.org/wiki/Computational_complexity_theory However, in papers, there are a lot of important new classes which are rarely found, such as…
user39815
1
2 3
…
8 9