Questions tagged [complexity-classes]

Computational complexity classes and their relations

Filter by
Sorted by
Tagged with
-1
votes
0answers
61 views

Verifier definition of NP/poly

I would like to know whether there is a definition of the class NP/poly in terms of (deterministic) polynomial time verifiers. The following is the definition of NP/poly I see everywhere (other than ...
2
votes
1answer
131 views

What graphs on $\mathbb{N}$ can be encoded as regular languages?

Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
0
votes
0answers
178 views

Unambiguous Problems and Classes over Reals

Are there unambiguous analogues of $NP_{R}$ (using the BSS model, in all discussion)complete problems, and any results known about them? For instance, the canonical $NP_{R}$ complete problem $4FEAS$ (...
18
votes
1answer
1k views

Has parameterized complexity led to better algorithms?

I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
2
votes
1answer
99 views

Complexity of type inference in the simply typed lambda calculus

A similar question was answered here: Is simply typed lambda calculus equivalent to primitive recursive functions What I conclude from the answers is that the complexity is that of the extended ...
1
vote
1answer
56 views

Rademacher Complexity of the Composition with an Indicator

Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \...
1
vote
1answer
75 views

Can a NEXP machine simulate invalid queries to a promise problem oracle?

Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output ...
1
vote
0answers
64 views

Reference to “compressibility” of logarithmic space [closed]

Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ...
1
vote
1answer
75 views

Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments

Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties: The size of $\psi$ is ...
6
votes
0answers
83 views

Counting on grid graphs

Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs? Since there seem to be ...
6
votes
1answer
131 views

Complexity of approximating a real function using queries

Consider the following computational problem, where $I$ is the real interval $[-1,1]$: There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of ...
-5
votes
1answer
104 views

Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
3
votes
1answer
138 views

Are all RegExp solvable in O(n)?

I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns ([abc]+);\1 ...
1
vote
1answer
117 views

Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
4
votes
0answers
116 views

Why can MIP be restricted to just two provers?

In several places I see it referred to that the MIP class can be assumed to be two interactive provers that don't communicate with each other, rather than any polynomial number of provers. Why are ...
12
votes
2answers
253 views

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, ...
7
votes
1answer
163 views

Complexity class of efficient streaming algorithms

Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words: $L \in \mathsf{StreamL}$ if there ...
5
votes
0answers
121 views

Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By ...
10
votes
1answer
276 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
97 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
114 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 ...
6
votes
1answer
146 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
91 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
172 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
165 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
52 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
89 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
269 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
143 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
129 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
75 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
101 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
302 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
142 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} =...
2
votes
1answer
78 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
169 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
196 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
177 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
310 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 $|...
22
votes
2answers
820 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
136 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
944 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
137 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
117 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
164 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
174 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 ...
4
votes
0answers
78 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
143 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
2 3 4 5
12