Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
314
questions
0
votes
0answers
14 views
$P$ with $SAT[k]$ and $NP[k]$ oracles?
We know $coNP$ is in $P^{NP}$ and so does $coNP$ in $P^{NP[1]}$ and $P^{SAT[1]}$ hold?
Is there a difference between $P^{SAT[k]}$ and $P^{NP[k]}$ at any $k\geq0$?
0
votes
0answers
40 views
Intersection of decision problems?
Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
0
votes
1answer
40 views
prove that there is a complete language in $L \cup \{A_{TM}\}$
$A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$
$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space
Given the language $L ...
2
votes
0answers
29 views
Is PSPACE vs NEXPTIME known?
I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME.
Is anything known about ...
1
vote
1answer
20 views
Problem class of assigning N persons to N tasks, zero costs with prefs
I am looking for the general problem class / computational complexity / algorithms for the following problem:
N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice ...
1
vote
2answers
19 views
Why do we use worse-case when categorising problems?
Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis.
Why don't we use the average case?
I imagine we could have a problem ...
1
vote
2answers
68 views
DSPACE(f(n)) closed under complement
I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$...
0
votes
1answer
118 views
Proving NP completeness of maximal length path
I have this question to answer:
For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
2
votes
1answer
24 views
NL-Hardness of Target
When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve:
$ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...
0
votes
1answer
34 views
A simple clarification on polynomial hierarchy
$P^{NP}\subseteq BPP^{NP}$ holds. According to current knowledge $BPP$ is in $\Sigma_2^P\cap\Pi_2^P$ holds. So according to current knowledge is following true?
$P^{\Sigma_2^P\cup\Pi_2^P}\subseteq ...
0
votes
0answers
18 views
Why is $BPP^{NP}$ in the polynomial hierarchy?
Why is $BPP^{NP}$ in the polynomial hierarchy?
I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. Should I just simply reuse the proof of $BPP\subset NP^{NP}$, feed in each machine ...
0
votes
0answers
30 views
is this given language in class P? [duplicate]
i was wondering:
is this language in class P?
$NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$
explanation: a ...
0
votes
1answer
25 views
Can CNF with an input string be evaluated in logarithmic space?
I have been trying to solve satisfiability of
{$<c, w>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}.
As first looks to me, it is satisiable in linear time ($O(n)$) since ...
2
votes
0answers
25 views
On the robustness of BQP class
Typically the notion of quantum Turing machine is introduced with its transition function.
$$
\delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}}
$$
Where $\mathbb{C}'\...
1
vote
1answer
24 views
Changing probabilities to 0/1 in definition of class IP
A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$,
$$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$
$$w\notin L\Rightarrow Pr[V\...
3
votes
1answer
64 views
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?
If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens? Does it imply $NP\neq EXP$? Is there any other consequences such as $BPP\neq EXP$? Does it also give $PSPACE\subseteq DTIME[n^{O(\log n)}]$?
0
votes
0answers
33 views
Reduction of complement from complexity class co-np and p
Let P $ \neq $ NP.
D is in the complexity class co-NP.
B is in the complexity class P.
Let $ \bar{D} $ be the complement of D, then $\bar{D} $ $\leq _ {p} $ B.
Is this statement true or false? My ...
1
vote
1answer
24 views
Show: “Checking no solution for system of linear equations with integer variables and coefficients” $\in \mathbf{NP}$
I've been struggling for a while trying to solve this problem:
Show that the following problem is in $\mathbf{NP}$:
Check that a system of linear equations with $m$ integer variables and
integer ...
1
vote
1answer
35 views
Proof of proposition between Precise Turing Machine and Proper Complexity function
In "Computational Complexity" textbook by C. H. Papadimitriou, p. 141, he proved the following claim.
Proposition 7.1: Let there be a DTM/NDTM M that decides a language L within time/space $f(n)$, ...
1
vote
2answers
34 views
NP-hardness does not imply lower bound, strictly speaking?
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.
Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
1
vote
0answers
8 views
$NC$ and $FNC$ oracles low for functional and Stockemeyer classes respectively?
We know $P^{NC}=P$ and $FP^{FNC}=FP$ hold. Do $FP^{NC}=FP$ and $P^{FNC}=P$ hold?
1
vote
1answer
11 views
Alternative formulation of complexity class $BPP$
In Aurora and Barak, they give the following alternative definition of $BPP$:
What is the meaning of the subscript to $Pr$? Is that $Pr_{r \in_R \{0,1\}^{p(|x|)}}$? My guess is this is supposed to ...
1
vote
0answers
13 views
Other problems in UP and co-UP
Are there any known problems in $UP \cap co-UP$ other than integer factorization and parity games (or a problem that can be reduced in polynomial time to either problem), that aren't known to be in $P$...
0
votes
1answer
46 views
Why all problems are not in P complexity?
İf Somebody wants to play perfect chess.I consider for finding solution to this problem,possible minimum data compression method which describes with 10 bit maximum possible data is in the range of 2^...
1
vote
0answers
20 views
Complexity class without fixed-poly size circuit
$PP$ is shown to have no fixed-poly size circuit by Vinodchandran.
Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan.
In notation, ...
0
votes
0answers
30 views
$\mathbb{NEXP\subseteq(NEXP\cap coNEXP)/poly}\implies \mathbb{NEXP=NEXP\cap coNEXP}$
We already know that $NEXP\subseteq EXP/poly\implies NEXP=EXP$. What if we change $EXP$ to $NEXP\cap coNEXP$.
As the title states, prove the statement in the title.
The original proof use the self-...
0
votes
1answer
21 views
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
What if an $L$-complete problem has $NC^1$ circuits? More generally, what evidence is there against $NC^1=L$?
2
votes
1answer
44 views
Relationship between complexity classes XP and W[1]?
I am reading the introductory chapter in Parameterized Algorithms by Cygan et al. and I am having some problems with the distinction between complexity classes $\mathsf{W[1]}$ and $\mathsf{XP}$.
...
4
votes
1answer
223 views
Is exponentiation in P?
I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?
Inputs: two numbers $(a,b) \in \mathbb{N}$
Output: $a^b$
0
votes
1answer
36 views
Will such an algorithm be feasible, will it be considered a poly time algorithm?
Given a p-digit number n, where p is atleast 500, if we have an algorithm whose computational complexity is in the worst case,
$O(p\mathrm{log}(p))$,
will it be counted as a poly time algorithm ? Or ...
0
votes
1answer
147 views
Modular exponentiation running time
I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student).
Is it poly ...
1
vote
1answer
34 views
If a language is contained in other langauge, is it of the same complexity?
If some language $L$ is in P, and some other language $K$ is contained in $L$, does that mean that $K$ is also in P?
Thanks :)
0
votes
1answer
18 views
$\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$
Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.
For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.
1
vote
1answer
107 views
P=NP giving a deterministic algorithm for SAT
I'm trying to prove the following problem:
Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $\phi$.
OUTPUT: A satisfying ...
1
vote
1answer
25 views
Hardness of $2$ edge-disjoint spanning trees decomposition
The question is clear from the title. What is the complexity of the following decision problem:
Input: An undirected graph $G(V, E)$
Output: $\mathrm{YES}$ if $G$ can be decomposed into two ...
2
votes
1answer
109 views
Show that RP is closed under concatenation
I'm trying to prove the following problem:
Show that $RP$ is closed under concatenation
Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the ...
1
vote
1answer
59 views
Looking for a problem provably not in P
My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. ...
2
votes
1answer
27 views
Is there a complexity class “BQP without error”?
I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm ...
1
vote
0answers
25 views
What if $PSPACE$ falls to non-uniformity?
We know if every language in $EXP$ has polysize circuits, then $P\neq NP$ and $EXP=PSPACE=\Sigma_2^P\cap\Pi_2^P$.
If every language in $PSPACE$ has polysize circuits, then does it give anything (note ...
0
votes
0answers
32 views
Does floor and ceiling in LP implies more than $P=NP$?
We know ability to take floor and ceiling in Linear Programming (LP) implies $P=NP$ (just apply floor and ceiling to variable in $(0,2)$ to get binary variable and from this it follows $0/1$ ...
3
votes
1answer
100 views
Is $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$?
We know that $\mathsf{DSPACE}(\log\log n) = \mathsf{DSPACE}(1)$ according to this proof.
Can we claim that $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$ or something like $\mathsf{DSPACE}(n^3)=\...
1
vote
1answer
40 views
Question on time hierarchy [closed]
How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$?
(sorry about how it is written. I mean the set of languages decided by a deterministic ...
2
votes
0answers
26 views
Do undecidable problems have no HO query? If so, could I have an example?
In descriptive complexity, HO corresponds to ELEMENTARY.
ELEMENTARY is a subset of R, so therefore all HO queries are decidable.
Then undecidable problems have no corresponding HO query. Is my ...
0
votes
2answers
91 views
Defining decision-problem complexity classes by counting branches of a polynomial-time NTM
This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) ...
5
votes
1answer
107 views
Have any natural complexity classes been proven not to be closed under complement?
Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be?
I'm sure one could construct some contrived ...
1
vote
1answer
126 views
Assumption: A PSPACE-hard problem can be solved in polynomial time
Under the assumption that a PSPACE-hard problem A can be solved in polynomial time, is the following argumentation valid?
Since every problem in PSPACE can be ...
0
votes
0answers
51 views
Decidability of language that contains all TM encodings that accept at least one word
I have a language that contains all encodings of the Turing machines that accept at least one word.
Is this language recursive, recursively enumerable, or neither?
3
votes
1answer
92 views
Is $NP\subseteq DTIME(2^{\theta(\sqrt n)})$ never possible?
$DTIME(2^{\sqrt n})$ is not closed under polynomial changes of $n$ however $DTIME(2^{polylog(n)})$ is.
So if $3SAT$ were in $DTIME(2^{polylog(n)})$ then $NP\subseteq DTIME(2^{polylog(n)})$ holds.
...
0
votes
2answers
73 views
From $P=NP$ to $NP=NL$
Does $P=NP$ implies $3SAT$ reduces to $2SAT$?
If so then from $2SAT$ is $NL$-complete can we conclude $NP=NL$?
2
votes
1answer
43 views
Is it known that $AC^1 \subseteq L$?
A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ ...
