Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
1
vote
1answer
20 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
37 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
23 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
13 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
26 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
30 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
10 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
21 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
18 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
36 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
219 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
97 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
17 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
102 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
23 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
66 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
58 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
26 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
24 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
29 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
84 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
35 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
25 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
70 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
88 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
96 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
40 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
91 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
62 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
34 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$ ...
2
votes
1answer
103 views
Is every PSPACE-complete problem complete with respect to logspace reductions?
A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$,
$$
A \le_L ...
-1
votes
1answer
73 views
On NP and PP in RP?
Does $NP\subseteq RP\implies NP=RP$?
Does $PP\subseteq RP\implies \oplus P=NP=RP$?
At least what additional minimal conditions will give truth of above?
1
vote
1answer
24 views
Complexity for nested #P?
Consider a problem such as weighted model counting for propositional logic. The problem of enumerating all models M of a logic formula ...
3
votes
2answers
82 views
Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?
This "research vignette" (whatever that is) claims that the polynomial hierarchy
classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of ...
2
votes
1answer
47 views
Comparison between MA and $P^{NP}$
I am aware that $MA \subseteq ZPP^{NP} \subseteq \Sigma_2^{P}\cap \Pi_{2}^{P}$ and also $NP^{BPP} \subseteq MA \subseteq AM \subseteq \Pi_{2}^{P}$.
My question is: In this whole thing, where does $P^{...
3
votes
1answer
90 views
Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?
It is within polynomial hierarchy so I assumed it is decidable. The picture like this further hinted in that direction.
Yet, in a paper on page 2 I read
Satisfiability of [...] is highly ...
0
votes
1answer
67 views
PSpace-completeness under PSpace reductions
A language $L$ is PSpace-complete, if it meets two conditions:
It is in PSpace.
Every other PSpace-complete language reduces to it in polynomial time.
Question: suppose we change the second ...
0
votes
1answer
37 views
$UP=BPP$ implies $UP=RP$?
https://cseweb.ucsd.edu/~mihir/cse200/ss6.pdf shows $NP$ in $BPP$ implies $NP$ in $RP$ by showing $SAT$ is in $RP$ if $NP$ is in $BPP$ and since $SAT$ is $NP$ complete we have $NP$ is in $RP$.
...
2
votes
1answer
67 views
Why doesn't this put $BPP$ in $NP$?
From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$
From Adleman we know $x\in L(M)...
0
votes
1answer
53 views
On clarification of intersection of classes definition
How do you define $\oplus P\cap PP$?
$L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0$.
$L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x)$.
Consider ...
0
votes
1answer
46 views
$\#P$ closure under binomial coefficients? [closed]
It is quite straightforward to understand $\#P$ closure under addition and multiplication since there are canonical $NTM$ constructions.
Is there illustrative non-trivial example to understand $NTM$ ...
-1
votes
1answer
36 views
Why is $MOD_{p^k}P=MOD_pP$ at every prime $p$?
Complexity zoo states that $MOD_{2^k}P=MOD_2P$.
It is clear that if $MOD_2P$ accepts (number of accepting paths is off) then $MOD_{2^k}P$ accepts.
Why is it clear that if $MOD_2P$ rejects (number of ...
0
votes
2answers
47 views
A simple clarification on $\#P$ closure properties
What does $\#P$ closure under addition and multiplication mean?
Does it mean given $NTM$s $N_1$ and $N_2$ we can create in deterministic polynomial time an $NTM$ $N_\times$ and $N_+$ such that for ...
2
votes
1answer
36 views
Is there a name for this class?
The class $C_{1,\epsilon }$ of decision problems solvable by an NP machine such that
If the answer is 'yes,' at least 1/2 and at most $1-\epsilon$ of computation paths reject.
If the answer is 'no,' ...
