Questions tagged [complexity-classes]
Computational complexity classes and their relations
556
questions
10
votes
1answer
215 views
The theoretical complexity of Go - The state of the art
What are the latest advances in theoretical complexity of Go?
I know some early works about the complexity of Go:
"Go is polynomial-space hard" proved that Go is PSPACE-hard.
"Ladders are PSPACE-...
-2
votes
0answers
39 views
performance vs complexity given an optimization problem
Newbie here.
I want to read a few papers on the theory of the performance of an algorithm vs its complexity for a given problem. I will give an example shortly but my aim is to find papers, books, ...
2
votes
0answers
94 views
Is PP invariant under changing its cut-off from 1/2 to another number?
Suppose I have a fixed family of quantum circuits $\{C_i\}$ for which determining whether the maximum output acceptance probabilities are $p\geq 1/2$ or $p< 1/2$ is PP-hard.
Now suppose I have the ...
0
votes
2answers
104 views
Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? [closed]
Arora and Barak define NP-completeness as the following:
"We say that a language $A \subseteq \{0, 1\}^∗$
is polynomial-time Karp reducible to a language
$B \subseteq \{0, 1\}^∗$
denoted by
$A \leq_p ...
4
votes
1answer
114 views
Is $L \subset 1NL$ when $L \neq NL$?
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
0
votes
0answers
79 views
Are there complexity theory consequences of the collapse NEXP=EXP^NP?
It is clear that $NEXP\subseteq EXP^{NP}$, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse $EXP^{NP}\...
1
vote
0answers
18 views
Sorting using comparisons that are not simple mappings of simple comparisons
The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
2
votes
2answers
162 views
Problem in deterministic time $n^p$ and not lower
I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable).
...
9
votes
1answer
150 views
Containment problem of an acyclic NFA in an NFA
Let $A$ and $B$ be NFAs, such that $A$ is acyclic.
In the general case, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$-hard. However, since $A$ is acyclic, we know that for every $w \in L(A)$, it ...
0
votes
0answers
46 views
Randomized Reduction for Maximization Problem
I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
2
votes
0answers
87 views
What is the difference between ${\bf P ^{\bf FewP}}$ and ${\bf UP ^{\bf FewP}}$?
What is the difference between ${\bf P ^{\bf FewP}}$ and ${\bf UP ^{\bf FewP}}$ ? In other words, what is the language that can be decided by ${\bf UP ^{\bf FewP}}$, but cannot be decided by ${\bf P ^{...
4
votes
0answers
75 views
BPP fragment of a PSPACE complete problem
Consider a PSPACE-complete problem (e.g., TQBF).
Is there a sub-problem in BPP, that is not known to be in P?
Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e....
5
votes
1answer
190 views
If NP in BPP then NP equals RP
I am looking for a reference to the fact that if NP is included in BPP then NP is equal to RP. See for instance these links:
https://cs.stackexchange.com/q/80509
http://www.inf.ed.ac.uk/teaching/...
1
vote
1answer
86 views
The decision procedure of theory of closed real field is in NP-hard?
The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
4
votes
0answers
127 views
Terminology: FNP, with P replaced by NP?
Consider these two classes of search problems:
Search problems with poly-sized solutions s.t. verifying solutions is in P.
Search problems with poly-sized solutions s.t. verifying solutions is in NP.
...
0
votes
0answers
70 views
Does Descriptive Complexity techniques have the naturalisation barrier?
I wished to know if the proof attempts at separation of complexity classes via the methods outlined by Descriptive Complexity theorists naturalise?
By naturalise I'm talking about the Idea of Natural ...
3
votes
1answer
96 views
Term for a set that is not immune
At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and ...
4
votes
1answer
297 views
Which complexity class does this problem belong to?
Consider the following problem $\mathcal{P}$.
Instance: A Boolean formula $F$ of $n$ Boolean variables ($x_1,...,x_n$) and $m$ Boolean parameters ($b_1,...,b_m$) where $0 \leq m \leq n$.
Problem: ...
3
votes
1answer
139 views
Co-NP definition
The class Co-NP is defined as all the languages $L$ such that $\overline{L} \in NP$. An example that appears in the book of Arora and Barak is of $\overline{SAT}$, which is defined as $\overline{SAT} =...
1
vote
1answer
73 views
Are there common names for the subtiers of PTIME?
We all know P, or PTIME, I think, as a common name for the class of polynomial-time problems. Are there common names for the first few levels inside P; that is, for constant-time, linear-time, ...
4
votes
1answer
162 views
On complexity class $\mathsf{\Pi_2 L}$
I suggest the following definition of $\mathsf{\Pi_2 L}$ (similarly to the certificate definition of $\mathsf{NL}$):
A language $L$ belongs to $\mathsf{\Pi_2 L}$ iff there exists a deterministic ...
10
votes
0answers
187 views
On Courcelle's question about Monadic second-order logic with cardinality predicates
I have found the following question at openproblemgarden.org:
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the ...
8
votes
0answers
151 views
A canonical complete problem for EXP and NEXP in terms of formulae
3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE.
Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen ...
11
votes
0answers
307 views
Is unary $\Pi_2$-SUBSETSUM coNP-complete?
Consider the following problem:
for given integers $a_1, \ldots, a_{2n}$ and $A$ that are given in unary representation
define is it true that
for every $S \subseteq \{1, ..., 2n \}$ such that $|...
20
votes
2answers
669 views
PPAD and Quantum
Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
5
votes
1answer
134 views
Consequences/existence of problems without any “optimal” algorithm
Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off ...
13
votes
3answers
848 views
A game on several graphs
Consider the following game on a directed weighted graph $G$ with a chip at some node.
All nodes of $G$ are marked by A or B.
There are two players Alice and Bob. The goal of Alice (Bob) is to ...
-4
votes
1answer
83 views
what does NP ⊆ DTIME(…) mean?
Recently I've seen inside theory of a paper. This time complexity, DTIME, is completely new for me. Can somebody explain it?
Also, the paper shows that the misinformation containment problem cannot ...
6
votes
1answer
106 views
Separation of AM and SZK
Are any results on the separation of AM from SZK known (e.g. relativized separation, or a separation assuming one-way functions exist, etc.)?
2
votes
1answer
157 views
Possibility of hierarchy with $UP$ class?
I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
0
votes
1answer
165 views
Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?
If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is ...
3
votes
0answers
70 views
$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?
Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following:
$FPT = XPuniform\implies EPTAS = PTAS$.
Fundamentals of Parametrized complexity on page $534$ has
...
2
votes
0answers
141 views
Is the following problem in $coNP$?
Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$?
At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
-1
votes
1answer
89 views
Why is $BPP^{NP}$ in polynomial hierarchy? [closed]
Why is $BPP^{NP}$ in the polynomial hierarchy?
I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. However, how does that imply $BPP^{NP}$ is inside the polynomial hierarchy?
7
votes
1answer
258 views
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
3
votes
1answer
193 views
String theory based computations
I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of ...
1
vote
0answers
121 views
Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$
Given a $\Sigma^p_2$-complete oracle (i.e., $\Sigma_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function ...
8
votes
0answers
116 views
Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?
Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another.
However, if we consider larger complexity classes such as ...
11
votes
0answers
205 views
Computational Complexity of the Frobenius Problem
The Frobenius problem takes as input $n$ positive integers $a_1,\ldots,a_n$ with $\gcd(a_1,\ldots,a_n)=1$ and asks for the largest integer $F$ that cannot be written in the form $F=a_1x_1+a_2x_2+\...
1
vote
2answers
107 views
When is a problem specified on a TM contained in non-uniform classes such as P/poly? [closed]
In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
6
votes
1answer
244 views
Example problem that is not in $2^{o(n)}$ but could be solved in $O(2^{cn})$ for any $c > 0$ (suggested by wording of ETH)
In the wikipedia article on Time Complexity it is written that:
The exponential time hypothesis (ETH) is that 3SAT, the satisfiability problem of Boolean formulas in conjunctive normal form with, ...
-3
votes
1answer
91 views
Are there any known languages in the intersection of NP and co-NP but not in P? [closed]
We currently don't know the relationship between NP and co-NP, but would it be possible to show whether the intersection is equal to P? I can't think of any languages in both NP and co-NP, but not in ...
10
votes
1answer
170 views
Natural candidates for NP-E and E-NP
It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$...
14
votes
0answers
452 views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
0
votes
3answers
263 views
Hamiltonian cycle vs co-NP [closed]
I am trying to understand co-NP and its implications properly.
The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows:
...
1
vote
0answers
279 views
EXPSPACE proof and its implications
I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below.
\begin{equation} \label{eq:nip_obj}
\min_{x \in \Phi} \sum_{i = 1}^n ...
1
vote
0answers
71 views
Complexity of enumerating over promise problems and circuits?
Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
11
votes
1answer
275 views
Is DSPACE(n) = DSPACE(1.5n)?
From space-hierarchy theorem it is known that if $f$ is space-constructible then
DSPACE($2f(n)$) is not equal to DSPACE($f(n))$.
Here, by DSPACE($f(n))$ I mean the class of all problems that can ...
7
votes
1answer
198 views
Does Max Planar 3-SAT admit a PTAS?
Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
7
votes
1answer
335 views
“Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?
Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you ...
