50 votes
Accepted

Why do we believe that PSPACE ≠ EXPTIME?

Let's refresh the definitions. PSPACE is the class of problems that can be solved on a deterministic Turing machine with polynomial space bounds: that is, for each such problem, there is a machine ...
user avatar
40 votes

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

No, there will be absolutely no implication, for several reasons: The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard ...
user avatar
21 votes

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

No implications are known either way: classical simulation of quantum computers tells us nothing about how hard NP search problems are; fast solutions to NP search problems tell us nothing about how ...
user avatar
18 votes
Accepted

Why is NP in EXPTIME?

Any problem in NP is in EXPTIME because you can either use exponential time to try all possible certificates or to enumerate all possible computation paths of a nondeterministic machine. More ...
user avatar
17 votes

Is the class NP closed under complement?

First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science. If $\sf P= NP$, ...
user avatar
  • 11.9k
17 votes
Accepted

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

All the classes you mention are classes of languages, formally, even if P and NP are often discussed in different (more sloppy?) terms. Note that terminology revolving around decision problems is ...
user avatar
  • 70.8k
16 votes
Accepted

PTAS definition vs. FPTAS

Let me answer your questions in order: By definition, a problem has an FPTAS if there is an algorithm which on instances of length $n$ gives an $1+\epsilon$-approximation and runs in time polynomial ...
user avatar
14 votes
Accepted

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

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case. If, however, $P \neq NP$, ...
user avatar
  • 1,904
14 votes
Accepted

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

It depends on what definitions you use. Sipser [1] defines $\mathrm{SPACE}(f(n))$ to be the class of languages decided by Turing machines using $O(f(n))$ cells on their work tapes for inputs of ...
user avatar
14 votes
Accepted

Can any problem in P be converted to any other problem in P in polynomial time?

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$. Here "non trivial" means that $B$ has at least ...
user avatar
  • 22.7k
13 votes
Accepted

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

The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in ...
user avatar
13 votes
Accepted

What is practical difference between NP and PSPACE-complete?

I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to ...
user avatar
12 votes
Accepted

If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

Your prof was absolutely not rigorous (i.e. completely wrong), that's why the distinction between NP and co-NP doesn't make sense with his definition. Better definition: Def.: A decision problem (...
user avatar
  • 24.9k
11 votes

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

From the P vs. NP and the Computational Complexity Zoo video. For a computer with a really big version of a problem... P problems easy to solve (rubix cube) NP problems hard to solve - but ...
user avatar
  • 223
11 votes

Why do we believe that PSPACE ≠ EXPTIME?

A machine running in exponential time could use exponential space. So a priori it could be that machines restricted to polynomial space would be weaker. A similar situation occurs for P and L. A ...
user avatar
11 votes
Accepted

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

There are very many natural complete problems for $\Pi_2^p$, and there is a survey [1] on completeness for levels of the polynomial hierarchy, containing many such problems. The paper On the ...
user avatar
  • 13.2k
11 votes

Relationship of algorithm complexity and automata class

Here are some known results: $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular ...
user avatar
11 votes
Accepted

Complexity classes pertaining to listing all solutions?

The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a ...
user avatar
  • 1,271
9 votes
Accepted

Does #$P$-Completeness imply approximation hardness?

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ [3]. (In the model he ...
user avatar
9 votes
Accepted

Decision problem which belongs to P reduced to a decision problem which belongs to NP?

Of course. Just take B=A, since every P problem is in NP.
user avatar
9 votes
Accepted

Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?)

The Definitions This comes from the one-sidedness of the definition $NP$, that (we think) is inherent to the class. One definition of $NP$ is the set of languages $L$ such that there is some for ...
user avatar
  • 29.1k
9 votes
Accepted

Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

The reduction takes time to perform. You know that time is polynomial but you don't know it's linear so you can't conclude that $L\in \mathrm{NTIME}(n)$. You can only conclude that $L\in\mathrm{NTIME}(...
user avatar
9 votes
Accepted

space complexity of DFA intersection problem

Solving intersection Non-Emptiness for 2 DFA's: It essentially just becomes a reachability problem for the product DFA. Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ ...
user avatar
9 votes

is Co-NP in PSPACE?

By the same reasoning that NP is in PSPACE, co-NP is in co-PSPACE. But co-PSPACE = PSPACE (you can just flip the answer), so co-NP is in PSPACE, too.
user avatar
9 votes
Accepted

Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for some constant implicit in $O$, in other words, it is the union of the $\mathrm{DTIME}(cn)$ for all $c&...
user avatar
  • 318
9 votes
Accepted

Why does P/Poly can also receive bad advice?

Lets review the definition of the class $P/poly$ by Turing machines which take advice. The class $T(n)/a(n)$ is the set of languages decidable by a Turing machine which runs in time $T(n)$ with ...
user avatar
  • 13.1k
9 votes
Accepted

Why is PH in PSPACE?

No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, ...
user avatar
9 votes

What is the relation between EXPTIME and NP HARD complexity classes?

There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, ...
user avatar
  • 687
8 votes
Accepted

Are there established complexity classes with real numbers?

Yes. There are. There is the real-RAM/BSS model mentioned in the other answer. The model has some issues and AFAIK there is not much research activity about it. Arguably, it is not a realistic model ...
user avatar
  • 21.6k
8 votes

Are there established complexity classes with real numbers?

The model you describe is known as the Blum-Shub-Smale (BSS) model (also Real RAM model) and indeed used to define complexity classes. Some interesting problems in this domain are the classes $P_R$, $...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible