Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
94
questions with no upvoted or accepted answers
10
votes
1
answer
473
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 ...
- 201
10
votes
0
answers
159
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 ...
- 580
5
votes
0
answers
221
views
Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?
I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P?
The language ...
4
votes
0
answers
37
views
What is a term for a problem that is hard to approximate within a factor $c$?
Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. ...
- 5,994
4
votes
0
answers
52
views
Barriers to separating other complexity classes
Do Natural Proofs, Relativization and Algebrization also affect separation of other complexity classes like $L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$ etc?
- 2,891
4
votes
0
answers
452
views
PARITY using depth one TC0 circuit
I need to disprove that a PARITY gate can be simulated using a single MAJORITY gate, or even a ...
- 173
3
votes
0
answers
124
views
Is there a class for optimization problems with polynomial-time-computable bounds?
An optimization problem can be described by two functions $f$ and $g$, such that:
$f$ is a binary predicate representing the constraints: $f(x,y)$ is True if the output $y$ is feasible for the input $...
- 5,994
3
votes
0
answers
44
views
Given a complexity class C for problems which can be solved using exponential time and an exponential number of random bits. C ⊆ NEXP?
There must be a complexity class C that includes exactly the problems that can be solved in exponential time and having access to a truly random coin (which in turns implies that you will be able to ...
- 145
3
votes
0
answers
51
views
Does this EXPTIME-complete construction work for every DTIME?
I came up with the following after reading the Wikipedia page about EXPTIME, and I am wondering if I am right. I don't think I invented it, I just don't have any textbooks about this subject to find ...
- 141
3
votes
0
answers
58
views
Sufficient condition for a complexity class's closure under NP-reductions?
Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, ...
- 31
3
votes
0
answers
115
views
What about problems that are fixed parameter tractable with an algorithm that does not inspect the parameter?
A parameterized problem is a subset $L \subseteq \Sigma^* \times \mathbb N$, where $\Sigma$ is a finite alphabet. A parameterized problem is fixed parameter tractable, if it could be decided in time $...
- 1,439
3
votes
0
answers
59
views
Approximate algorithms for class P problems
As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra ...
- 131
3
votes
0
answers
545
views
Hardness of counting solutions to NP-Complete problems, assuming a type of reduction
The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
- 365
2
votes
0
answers
18
views
Properties of $\mathsf{PH}[1]$ and $\Sigma^{\mathsf P}_{poly(n)}[1]$?
$\mathsf{PH}[1]$ is a variant of a polynomial hierarchy in which each machine can only call its oracle once. $\Sigma^{\mathsf P}_{poly(n)}[1]$ is a polynomially "tall" tower of $\mathsf{NP}[...
- 1,632
2
votes
0
answers
37
views
What's the intuition behind MIP* being bigger than MIP?
It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$.
This was very confusing because it seemed like the (...
- 345
2
votes
0
answers
63
views
How to prove MIP is in NEXP
I was trying to understand the proof of MIP is inside NEXP. I was referring to Rutger's university scribes (link). They define MIP as a class with exponential proof, but that is not the definition I ...
- 243
2
votes
1
answer
75
views
Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
- 23
2
votes
0
answers
28
views
Are $\mathsf{L,NL}$ closed under reverse operation?
for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $.
My question is, are $\mathsf{L,NL}$ closed under ...
- 161
2
votes
0
answers
255
views
Is there a link between the "padding argument" and the "padding lemma"?
In computability theory here is what the padding lemma says :
Every partial recursive function $\phi_x$ has $\beth_0$ indices and for each $x$ we can find effectively an infinite set $C_x$ of indices ...
- 199
2
votes
0
answers
43
views
Rigorous Definition of a Complexity Class
From Wikipedia, "Complexity classes are sets of related computational problems. They are defined in terms of the computational difficulty of solving the problems contained within them with ...
- 213
2
votes
0
answers
66
views
Language in PSPACE that isn't PSPACE-hard and isn't in PH
Can there exist a language L in PSPACE such that L isn't PSPACE-hard and L isn't in the polynomial hierarchy (PH)? Intuitively, it seems like the answer is no, since TQBF is PSPACE-complete, and any ...
- 21
2
votes
0
answers
50
views
Complexity of approximating a function value using queries
I am looking for information on problems of the following kind.
There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You ...
- 5,994
2
votes
0
answers
70
views
Are there problems that are known to be in ZPP but not in p
Are there any problems that are known to be in ZPP but not in p?
- 356
2
votes
0
answers
88
views
Class of languages recognizable by n-bit formulas of size at most $T(n)$
A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-...
- 181
2
votes
0
answers
68
views
Proving a pattern exist in a string without revealing where
Some time ago i read the following problem (i don't remember the article from which i read it from) :
"Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), ...
- 54
2
votes
0
answers
270
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 ...
- 29.8k
2
votes
0
answers
33
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 ...
- 401
2
votes
0
answers
76
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 ...
- 2,891
2
votes
0
answers
61
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 ...
- 2,891
2
votes
0
answers
290
views
Proving that AM contained in Pi_2
i think that it's true that AM is contained in $\Pi_2$ but I'm not sure how to prove it. How do I prove that $AM \subseteq \Pi_2$?
- 91
2
votes
0
answers
45
views
Do we have to overcome any barriers for a proof of $VP\neq VNP$ proof?
Does the same barriers of relativization, natural proofs and algebrization affect a possible $VP\neq VNP$ proof?
How do existing strategies try to overcome these?
- 2,891
2
votes
0
answers
250
views
Relations between P^#P, NP^#P and (CO-NP)^#P
I was wondering if there were relation between the complexity classes
$P^{\#P}$, $NP^{\#P}$, $(Co-NP)^{\#P}$ ?(except the trivial inclusions)
I've the feeling that when taking a $NP^{\#P}$ machine, ...
- 21
2
votes
0
answers
57
views
Status of $BQP^{NP},NP^{BQP}$
The relation between $BQP$ and $NP$ is an open problem, while it seems that $BQP$ is somewhat lower for $NP$ than the other way round. Is the status of lowness of these problems known?
- 2,891
2
votes
0
answers
196
views
Proving $CVal$ is $RP$-hard
Let CVal be the language of all $<C,s>$ where $s$ is an $n-$tuple of binary values ($\{0,1\}$), such that $C$ is a variable-free boolean circuit (gates $\wedge$, $\vee$, $\neg$, $0$, $1$), and ...
- 523
2
votes
0
answers
37
views
crypto protocols from complexity class
Assume $P=PSPACE$. Then would it be possible to design cryptographic protocols based that is easy to compute from $PSPACE$ but hard to invert from something higher up in hierarchy?
A function $f: \{0,...
- 2,891
1
vote
0
answers
50
views
Is it known, whether the complement of NP-hard problems is necessarily again NP-hard?
Neither could I find any counterexamples, nor could I show that if indeed the complement of NP-hard problems was NP-hard, one could deduce some unknown results from it, which would imply that it is ...
1
vote
0
answers
85
views
Complexity of a variant of the Subset Sum Problem (second level polynomial hierarchy)
What is the complexity class of the following variant of the SSP problem:
Input: set of integers $\{x_1,\ldots,x_n\}$, integer $k$ and integer $T$.
Output: Yes, if there exists a subset $S\subseteq \{...
- 31
1
vote
0
answers
117
views
Proving EXP-Completeness for the Bounded Halting Problem
I am currently working on proving that the bounded halting problem is $EXP$-Complete. The bounded halting problem is defined by the language $L$ as follows:
$$L = \{\langle M,x,t \rangle : \text{...
- 11
1
vote
0
answers
28
views
Class of optimization problems whose decision versions are in P
NPO is defined to be the class of optimization problems whose decision versions are in NP.
I would like to get the complexity class of optimization problems whose decision versions are in P.
Is such ...
- 147
1
vote
1
answer
76
views
Decision version of optimization problems with polynomial-time approximation algorithms
Given an optimization problem $X$, it is easy to construct a decision problem $Y$, such that there is a two-directional polynomial-time reduction between $X$ and $Y$.
Therefore, we can define a class ...
- 5,994
1
vote
0
answers
77
views
Alternative outcomes of P versus NP
Given what we know, which of the following scenarios are possible:
There exist algorithms which are in-fact Ptime algorithms for NP-Complete problems, but which cannot be proved to work.
and there ...
1
vote
0
answers
46
views
How can $R_HL$ differ from $RL$?
https://complexityzoo.net/Complexity_Zoo:R
RL: Randomized Logarithmic-Space Has the same relation to L as RP does
to P. The randomized machine must halt with probability 1 on any
input. It must also ...
- 249
1
vote
0
answers
15
views
Decidablility of complexity properties and its relation to finite description method
We describe formal languages with their finite descriptions. For example we can describe a language simply by set-builder ( $\{ x : \phi(x)\}$) or we can describe something with its corresponding ...
- 368
1
vote
0
answers
35
views
$W$-hierarchy and parameterized search problems
I have two related questions:
What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
- 49
1
vote
0
answers
63
views
Consequence of NP-complete, and DP-complete w.r.t. randomized reductions
If a problem is NP-complete with respect to randomized (polynomial time) reductions, but not with respect to deterministic reductions, then we have P $\neq$ BPP (See Question 2 here and its answer).
...
- 155
1
vote
0
answers
59
views
An opposite method of padding argument on N/DTIME complexity class
Is there a method to prove things with longer input in complexity theory?
For example, using padding argument it's trivial to show that
$\text{NTIME}(n^2) \subseteq \text{DTIME}(n^4) \Rightarrow \...
- 21
1
vote
0
answers
189
views
What is the smallest time/space complexity class for which no sparse language is hard?
For example, whether there exists $\mathsf{PSPACE}$-hard sparse language an open problem, as it is not yet known whether polynomial hierarchy collapses.
But is it a solved problem for larger ...
- 1,632
1
vote
0
answers
32
views
Are there any "natural problems" which are known to be NPI under weak assumptions
Are there any "natural problems" which are known to be NPI under weak assumptions.
By weak assumptions I mean something like $P \neq NP$ or $NP \neq Co-NP$
- 356
1
vote
0
answers
32
views
Is $NC_1$ vs PP still an open problem?
Is $NC_1$ vs PP still an open problem?
I done a few searched but I can't find an answer.
- 356
1
vote
0
answers
99
views
What are some of the most ridiculous claims in computer science that we haven't disproved?
What are some of the most ridiculous possible claims in computer science that we haven't disproved?
E.g. For example the claim that ZPP=exptime is absurd but has not been disproven.
- 356