Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
259
votes
7answers
120k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
32
votes
2answers
8k views

Why do we believe that PSPACE ≠ EXPTIME?

I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, ...
29
votes
4answers
14k views

Generalised 3SUM (k-SUM) problem?

The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$. It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$....
25
votes
3answers
9k views

Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?
24
votes
1answer
14k views

Is the k-clique problem NP-complete?

In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete: Cliques have also been ...
20
votes
3answers
3k views

Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$?

Is it possible that $\mathsf{P} \not = \mathsf{NP}$ and the cardinality of $\mathsf{P}$ is the same as the cardinality of $\mathsf{NP}$? Or does $\mathsf{P} \not = \mathsf{NP}$ mean that $\mathsf{P}$ ...
15
votes
1answer
313 views

Complexity classes pertaining to listing all solutions?

I was reading a question over at Stack Overflow asking whether it was NP-hard to list all simple cycles in a graph containing a particular node and it occurred to me that I couldn't think of any ...
15
votes
2answers
3k views

Types of reductions and associated definitions of hardness

Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. ...
14
votes
2answers
563 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with ...
14
votes
2answers
607 views

Some questions on parallel computing and the class NC

I have a number of related questions about these two topics. First, most complexity texts only gloss over the class $\mathbb{NC}$. Is there a good resource that covers the research more in depth? ...
14
votes
1answer
497 views

Proof of Karp-Lipton theorem

I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009). In particular, this book states the following: Karp-...
13
votes
3answers
4k views

P, NP and specialised Turing Machines

I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the ...
13
votes
2answers
8k views

PTAS definition vs. FPTAS

From what I read in the ...
12
votes
1answer
484 views

What is complexity class $\oplus P^{\oplus P}$

What does the complexity class $\oplus P^{\oplus P}$ mean? I know that $\oplus P$ is the complexity class which contains languages $A$ for which there is a polynomial time nondeterministic Turing ...
12
votes
1answer
170 views

Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
11
votes
2answers
12k views

Is the open question NP=co-NP the same as P=NP?

I'm wondering this based on several places online that call $\sf NP=$ co-$\sf NP$ a major open problem... but I can't find any indication as to whether or not this is the same as $\sf P=NP$ problem...
11
votes
1answer
4k views

Why is NP in EXPTIME?

Is there an easy way to see why NP is in EXPTIME? It seems to me a priori conceivable that there could be a problem which requires super-exponential time to solve, but whose solution could be ...
11
votes
2answers
151 views

Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete. Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
11
votes
1answer
441 views

Complexity of deciding if a formula has exactly 1 satisfying assignment

The decision problem Given a Boolean formula $\phi$, does $\phi$ have exactly one satisfying assignment? can be seen to be in $\Delta_2$, $\mathsf{UP}$-hard and $\mathsf{coNP}$-hard. Is anything ...
11
votes
1answer
867 views

Collection of APX-hard problems

Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, ...
10
votes
5answers
14k views

Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
10
votes
1answer
403 views

Are there any natural $\Pi_2^P$-complete problems?

I know that the quantified Boolean formula problem for a formula $$ \psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi $$ where $\phi$ contains no quantifiers and only the ...
10
votes
1answer
1k views

Intuition behind Relativization

I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will ...
10
votes
2answers
533 views

Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$? I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the ...
10
votes
1answer
345 views

What do complexity classes look like, if we use Turing reductions?

For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this: (under standard conjectures). I'm sure we're all ...
10
votes
3answers
634 views

Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

I'd really like your help with proving the following. If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$. Here, $\mathrm{NTime}(n^{100})$ is the class of ...
10
votes
0answers
137 views

Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
9
votes
3answers
2k views

Concrete understanding of difference between PP and BPP definitions

I am confused about how PP and BPP are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions ...
8
votes
3answers
535 views

Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...
8
votes
1answer
969 views

What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other ...
8
votes
4answers
4k views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...
8
votes
3answers
206 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
8
votes
2answers
334 views

Why is one often requiring space constructibility in Savitch's theorem?

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
8
votes
1answer
96 views

Complexity class that properly included in DLOGTIME

Is there any decision problem that is in a complexity class properly included in DLOGTIME? (except $O(1)$, of course) If there is, can we create complete problems for DLOGTIME? So, can there be ...
8
votes
1answer
141 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
8
votes
1answer
197 views

is $P_{CTC} = BPP_{path}$?

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic. This is my reasoning, and I would like to know if (1) this is ...
7
votes
4answers
10k views

Is the class NP closed under complement?

Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.
7
votes
1answer
4k views

Are there any problems in complexity class EXP that are not in NP?

I cannot conceive of any problem that can be solved in exponential time, but cannot be checked in polynomial time.
7
votes
1answer
148 views

$\mathsf{2EXP} = \mathsf{EXP}^{\mathsf{EXP}}$?

It is clear that any language in $\mathsf{EXP}^{\mathsf{EXP}}$ can be computed in $\mathsf{2EXP} = \mathsf{DTime}(2^{2^{\mathsf{poly}(n)}})$. My question is whether the converse is true: is $\mathsf{...
7
votes
1answer
222 views

$\mathsf{PP=RP}$ consequences

We know $$\mathsf{PP=RP},\mathsf{coPP=coRP},\mathsf{PP=coPP=coRP=RP=ZPP=BPP\subseteq P/poly}$$ are equivalent and the polynomial hierarchy collapses to $2$nd level. What are the other non-trivial ...
7
votes
1answer
296 views

Select a subset of the columns in $2\times n$ matrix, is it easy?

I want to know if this problem is polynomial-time solvable or not? The problem is: Given a nonnegative integer-valued matrix of size $2\times n$ and two nonnegative integer numbers $b<n$ and $c$. ...
7
votes
1answer
544 views

Complexity of Monotone (+,2) SAT problem?

To continue this post, let us define the Monotone$(+, 2^-)$-SAT problem: Given a monotone CNF formula $F^+$, where each variable appears exactly once (as a positive literal), and a monotone 2-CNF ...
7
votes
1answer
6k views

NP $\subsetneq$ EXP?

I think I heard in somewhere that it has been proven that $\mathsf{NP}$ is strictly contained in $\mathsf{EXP}$, that is $\mathsf{NP} \subsetneq \mathsf{EXP}$. Is this right? Wikipedia and book ...
7
votes
1answer
891 views

Complexity of (SAT to 3-SAT) Problem?

It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables (see here). If using new variables is not allowed, it is not always possible (...
6
votes
1answer
2k views

Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)

NOTE: The statement of this question has a LOT of misconceptions. Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ? Form what I ...
6
votes
1answer
658 views

Notation: SPACE(n) vs SPACE(O(n))

I want to denote the class of problems solvable by linear space multi-tape Turing machines. I have seem in many places this class being denoted by $SPACE(n)$. But why is the notation $SPACE(O(n))$ not ...
6
votes
2answers
592 views

Proof of APSPACE = EXP

I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book. Please give a semi-detailed proof of this. I have found a paper which has this proof(by ...
6
votes
2answers
131 views

Analog of PP for computability rather than complexity?

The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the ...
6
votes
2answers
349 views

Complexity of “given a graph $G$ with vertex $v$, is there a maximum clique containing $v$”?

The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard). Another ...
6
votes
1answer
616 views

Known problems in BQP \ NP?

The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\...

1 2 3 4 5 7