Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
2
votes
1answer
103 views

$ACC^{0}$ vs Poly-size circuits of bounded degree

We know that NEXP $\not\subset ACC^0$ (Ryan Williams'10 Result). Also, We know that even $\Sigma_{2}^{P}$ cannot have polynomial circuits of bounded degree i.e. $SIZE(n^k)$ for some $k \in N$ (Kannan'...
0
votes
1answer
111 views

Clarification on class $SPP$?

A language $L$ is in $SPP$ if there is a $GapP$ function $f$ such that $x\in L\implies f(x)=1$ and $x\not\in L\implies f(x)=0$. By $x\not\in L$ I think we mean $x\not\in SPP$ correct? I would have ...
3
votes
1answer
206 views

Complexity Classes UP and US

According to complexity zoo: Class UP (Unambiguous Polynomial-Time) is defined as: The class of decision problems solvable by an NP machine such that If the answer is “yes,” exactly one computation ...
1
vote
1answer
134 views

Low for EXP and NEXP

What are the largest classes which are low for EXP and NEXP? For example: I am aware the class P, QP are low for EXP as well as NEXP. We also know that NP is not low for either of them. Is class ...
2
votes
1answer
64 views

On lowness of $\oplus P$

$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$). Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$? Are there complexity classes $\mathcal C$ ...
-1
votes
1answer
25 views

Some questions about the depth hierarchy of threshold circuits

Let me split my query into a few parts which possibly have overlapping answers, How do we prove that depth $3$ threshold circuits with polynomially bounded integral weights (call this $\hat{LT_3}$) ...
4
votes
1answer
305 views

Oracle Turing Machine EXP^EXP

I'm reading Arora Barak and in that it is written that when $O \in \mathrm{P}$, then $\mathrm{P}^O = \mathrm{P}$. Can this be generalized? Intuitively, I think that $\mathrm{NP}^\mathrm{NP} \neq \...
0
votes
1answer
658 views

If P=NP, which two languages are NOT NP-complete?

In my last exam this question got asked and i just cant find a clear answer: If P=NP, which two languages are NOT NP-complete? So I assume there are two special languages, but which? Thanks in ...
0
votes
1answer
57 views

How is it possible that $L_1$ is $NP$?

The question is from my complexity-theory course. The question If $L_1,L_2,L_3 \in \lbrace 0,1 \rbrace^*$, and different from $\lbrace 0,1 \rbrace^*$ and from the empty language, prove that if $L_1 \...
2
votes
2answers
459 views

Is NPSPACE also closed under polynomial-time reduction and under log-space reduction?

The complexity classes P, NP, and PSPACE are closed under polynomial-time reduction. The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction. I wonder if NPSPACE is also ...
1
vote
2answers
2k views

A problem is NP-hard iff its complement is coNP-complete

$A$ is NP-hard iff $\overline{A}$ is $coNP$-hard, where $\overline{A}$ does mean complement of $A$. I can't figure out why it is true. Let $A\in NP-hard$. I know that each problem in $NP$ is ...
1
vote
0answers
51 views

Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

Time hierarchy theorem states that $DTIME\bigg(o\Big(\frac{f(n)}{\log n}\Big)\bigg)\subsetneq DTIME\big(f(n)\big)$. However space hierarchy theorem is stricter in that point since it states $SPACE\...
1
vote
2answers
135 views

complexity theory NP [duplicate]

Ok, I really need help because I have read in so many books but still don't understand the complexity class NP. These are the books: Theoretische Informatik; Katrin Erk, Lutz Priese (german) ...
3
votes
1answer
183 views

Examples of problems for each class in $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$

Given that $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$ and that it is commonly believed that all these inclusions are strict can you provide examples of problems that are believed to be ...
2
votes
1answer
88 views

What is the relation of complexity class $L^L$ to other complexity classes?

What is the relation of complexity class $L^L$ to other complexity classes? (Here $L^L$ is the complexity class of decision problems solvable by a TM in logspace with an oracle for a language in ...
0
votes
1answer
285 views

Equivalence of machine $M$ in $BPP$ and $EXP$

Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists equivalent machine in $EXP$. I cannot see how the $EXP$-machine is ...
1
vote
1answer
286 views

Is an intersection between NPC and coNPC always DPC?

The class DP is defined as the set of all languages $L$ such that $L = L_1 \cap L_2$ where $L_1 \in NP$ and $L_2 \in coNP$. For example, the language SAT-UNSAT is defined in the following manner ($\...
1
vote
1answer
102 views

Confusing method of proving PSPACE-completness

I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me: We consider sequence (of polynomial length) of ...
0
votes
2answers
112 views

Asserting Run Time From Big O Function

Related to this, but I felt it was more appropriate to ask as a separate question: The complexity of Shor's algorithm is of order $$O\left(n^2\,\log(n)\,\log(\log(n))\right)$$ with $n$ the bit ...
0
votes
1answer
246 views

Never Brute Force?

Does there exist a more optimum algorithm to solve every problem than brute force (or an equivalent)? A brute force algorithm for the purpose of this question is defined as an algorithm of time ...
0
votes
0answers
93 views

Is there some problem in “promise-DSPACE(o(log log n))” that is also in “promise-DFA”?

Disclaimer I have no idea about complexity theory. If this question makes no sense or is wrong, mods are free to delete the question I´ve read somewhere that the problems that can be correctly ...
-1
votes
1answer
204 views

Query regarding PP complexity class vs NP?

Considering the complexity classes $NP$, $co-NP$ and $PP$: $NP$ and $co-NP$ are both contained in $PP$. For any Language $L$ suppose we have the mechanism that: If the oracle of $co-NP$ implies $No$ ...
1
vote
1answer
115 views

Demonstration that EXP is closed under union complementation and concatenation

How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?
6
votes
1answer
453 views

Is this graph problem NP-hard / NP-complete?

I have a certain kind of graphs. They are DAGs similar to dependency graphs but strictly hierarchical, that is, each node belong to a certain level in the hierarchy and cannot be moved up or down when ...
3
votes
1answer
556 views

What does the complexity class $\mathsf{XP}$ stand for?

$\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page ...
1
vote
0answers
67 views

On oracle access containment?

If $X,Y$ are complexity classes in the polynomial hierarchy with $X\subseteq Y$. With abuse of notation assume $X,Y$ also as the TMs that accept languages in classes $X,Y$ respectively. Then is it ...
1
vote
0answers
119 views

prove that $BPP(\alpha(n), \beta(n)) = BPP$

prove that for every $0 \le \alpha(n), \beta(n) \le1 \; s.t.$ there exists $c \in \Bbb{N} \;s.t \;\alpha(n)+\beta(n) \le 1- \frac{1}{n^c}$ then $BPP(\alpha(n), \beta(n)) = BPP$. I tried to show that ...
3
votes
1answer
119 views

Prove that $NP^{NP\cap co-NP} = NP$

Let $A\in NP\cap co-NP$. Then, $NP^A = NP$. At first, I thought: Easy, let $L\in NP^A$ s.t. $A\in NP\cap co-NP$. Let $M_L$, an $NDTM$ to decide $L$ and $M_A$, an $NDTM$ to decide $A$. Then, we could ...
5
votes
1answer
179 views

Space-unconstructable function in the proof of Savitch's theorem

I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it. The proof I'm talking about is the same as is currently on ...
1
vote
1answer
272 views

Non-deterministic logarithmic time complexity class

Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$? It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to ...
1
vote
1answer
203 views

Showing a problem is in coNP

We have the problem $C = \{<G,S>| \text{ S is a minimal cover of G }\}$ and we want to show that $C\in coNP$. I can easily show that there's a ND TM that decides $coC$ using a guess to check if ...
1
vote
1answer
99 views

What does $L$-uniformity mean?

I've understood that $L$-uniformity means that there's a TM that can output the description of $C_n$ in $O(\log n)$ space. Now, that seems odd to me since the description itself (as far as I ...
3
votes
2answers
123 views

Why 0-BPP equals P

Sorry if it is an obvious question, since all my searches lead to "clearly 0-BPP=P" (like Papadimitriou text book or Complexity Zoo). I understand that any P machine can be seen as a 0-BPP machine ...
1
vote
2answers
224 views

Decision problems whose verifier is NP

We define $\mathbf P$ as the set of problems solvable in polynomial time. We define $\mathbf{NP}$ as the set of problems with a verifier $ \in \mathbf P$. Is there a name for problems whose verifiers ...
2
votes
2answers
162 views

Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$?

I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some ...
25
votes
3answers
8k 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?
3
votes
1answer
192 views

Precise definition of oracle classes $A^B$

I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a ...
2
votes
0answers
55 views

A query on $\#P$ and $NP$?

We know that if a $\#P$-complete problem has a deterministic reduction to $FNP$ version of an $NP$-complete problem then polynomial hierarchy collapsed to first level. Is there a consequence if we ...
1
vote
0answers
209 views

Misunderstanding the Baker-Gill-Solovay oracle and obtaining $LOGSPACE^A=PSPACE^A$

Baker, Gill and Solovay [1] gave an oracle $A$ relative to which $P^A=PSPACE^A$. The oracle is the very simple $PSPACE^A$-Complete language $$A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \...
1
vote
1answer
276 views

Is UNIQUE-X3C a US-complete problem?

The problem: Exact Cover by 3-Sets (X3C) The definition: Given a set X, with |X| = 3q (so, the size of X is a multiple of 3), and a collection C of 3-element subsets of X. Can we find a subset C’ of ...
2
votes
1answer
424 views

Prove the following language is in L (LogSpace)

I'm trying to prove the following language is in $L$ (decided by a TM in $O(\log n)$ space): $$A = \{ (C,x) \mid C(x)=1\text{ and $C$ is a Boolean formula with depth }\log(n)\}\,,$$ where $n = |(C,x)...
0
votes
0answers
56 views

How does a given complexity class change under polynomial reduction?

Suppose we have a complexity class $C$ (say for example $C = DTIME(2^{cn})$). Take a language that belongs to $C$: $L \in C$. Define an arbitrary polynomial reduction from language $L$ to $L'$. To ...
0
votes
0answers
70 views

Equivalence between the two definitions of NEXPTIME complexity class

Wiki gives two definitions for the NEXP complexity class: $ \mathsf{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(2^{n^k}) $ where $\mathsf{NTIME}(f(n))$ is the set of decision problems that ...
4
votes
1answer
87 views

Can we multiply approximation hardness?

Say we have two (NP-)optimization problems $A$, resp. $B$, such that it is NP-hard to approximate within a factor $\alpha$ resp. $\beta$. Now define problem $C$ whose input consists of pair inputs ...
0
votes
1answer
214 views

Complexity class (P/NP) variants of Hamiltonian paths problems

I know that the following problems related to Hamiltonian paths in graph are NP-complete: Undirected Hamiltonian circuit: Given an undirected graph, does it has a cycle that passes through each node ...
0
votes
1answer
348 views

Complexity of Context Sensitive Languages

I was reading above complexity classes from Formal Languages and Automata book by Peter Linz. It gives following facts (in Theorem 5.2): Consider we have a CFG without null or unit productions. ...
1
vote
1answer
47 views

On different characterizations of $\mathsf P$

In here it was clarified that $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})\subsetneq\cap_{\epsilon>0}\mathcal C(n^{n^\epsilon})$ where $\mathcal C(t(n))$ is the class of problems solvable in $O(t(n)...
1
vote
2answers
1k views

Decision version of the traveling salesman problem and NP-hardness

Wikipedia says: The problem has been shown to be NP-hard and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-...
2
votes
1answer
537 views

Precise relation between complexity classes(focus on P, NP and EXPTIME)

I am interested in the precise relation between $P$, $NP$ and $EXPTIME$ classes. What I know so far: $P \subseteq EXP$ (from Time Hierarchy Theorem [1]) We don't know an exact relation between $P$ ...
4
votes
1answer
553 views

How to use succinct circuits to construct an EXPTIME complete problem?

When reasoning with NP-completeness, I find SAT and k-clique more convenient to reason with than generalized games that are NP-complete or the Turing machine model. I'm looking for something similar ...

1 2 3 4 5 7