Questions tagged [complexity-classes]
Computational complexity classes and their relations
591
questions
0
votes
0answers
31 views
Where is the following function in?
If a boolean function is in $UL\cap\mathsf{monotoneAC}^1$ and can be captured by evaluation problem of a circuit which is an $AND$-$OR$ circuit of $O(\log n)$ depth where $AND$ fan-in is $2$ and $OR$ ...
0
votes
0answers
104 views
Why do people refer to NP-complete as NP-hard? [closed]
Wikipedia describes binary integer programming NP-complete. However, it is also often referred to as NP-hard here and here. According to this Wikipedia explanation, completeness relative to a ...
1
vote
0answers
52 views
Consequences of an $o(\log n)$-approximation algorithm for a $\mathsf{\log\text{-}APX}$ hard problem
In [1], Feige proves that if there is a polynomial algorithm with approximation ratio in $o(\log n)$ for any $\mathsf{log\textit{-}APX}$ hard problem (say Minimum Dominating Set), then $\mathsf{NP}\...
3
votes
1answer
105 views
What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?
It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is ...
0
votes
0answers
65 views
On Determinant modulo $2^k$ complexity
Determinant of integer matrix modulo $2$ is complete for the class $\oplus L$. Is determinant modulo $2^k$ computable in $\oplus L$ at any fixed $k$?
How about if $k=o(n)$ where matrix is $n\times n$?
-2
votes
0answers
44 views
$\mathsf{NP}$-complete reduction efficiency and $\mathsf{NP}$-completeness of subexponential subsets of $\mathsf{NP}$ complete problems
Let $f:\{0,1\}^n\rightarrow\{0,1\}^m$ be from the family of functions $\mathcal F_{n,m}$ parametrized by lengths $n,m$. It is to say $f\in\mathcal F_{n,m}$ and let the cardinality of $\mathcal F_{n,m}$...
4
votes
0answers
136 views
The graph of problem reductions
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
-4
votes
0answers
38 views
TISP tradeoff bounds for $C$-uniform $TC^0$?
Let $C$-uniform $TC^0(n)$ be the class of functions computable by a $TC^0$ circuit of size $n$, where $C$ is DLOGTIME, LOGSPACE, or PTIME.
Is there a time-space $\mathrm{TISP}(t(n),s(n))$ bound for ...
0
votes
1answer
126 views
Comparing SAT to MCSP reduction class separations and faster SAT class separations?
Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $...
0
votes
0answers
68 views
What is the best reduction we know from flavors of $SAT$ to $MCSP$?
Consider $\mathcal P(n,m)$ to be a class from the set $\{k\mbox{-}\mathsf{SAT}(n,m),\mathsf{CIRCUITSAT}(n,m)\}$ where $k$ is fixed, $n$ is number of variables and $m$ is number of clauses.
Denote $\...
0
votes
0answers
47 views
Is anything known about NC$^1$ with NP oracle
A few things are known about the class $\textsf{L}$ provided with an $\textsf{NP}$ oracle ($\textsf{L}^\textsf{NP} = \Theta_2^\textsf{P}$ has attracted a bit of attention, for instance [1]) On the ...
2
votes
0answers
44 views
Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies
If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta_2^{\textsf{P}}$, sits at the top of the ...
5
votes
1answer
173 views
Where is $MA$ more relevant than $\exists BPP$?
(EDITED)
A previous version of this question asked about a complexity class I called $MA^*$, which has been recognized by users to be $\exists BPP$.
The difference between $MA$ and $\exists BPP$ is ...
0
votes
0answers
105 views
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\...
0
votes
0answers
4 views
Is base conversion in $\mathsf{TC^0}$?
$\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)$: Given an integer $\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}$ in binary output the $j$th binary digit of the $i$th base-$q$ digit (where $q$ is not necessarily a prime)...
2
votes
1answer
108 views
Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$? [closed]
A complete problem for $\mathsf{PPP}$ is the pigeon problem which is 'Given a Boolean circuit ${\displaystyle C}$ having the same number ${\displaystyle n}$ of input bits as output bits, find either ...
5
votes
1answer
207 views
Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?
Do we know if $\mathsf{ZPP}\subseteq\mathsf{UP}$ known or is there oracles against the hypothesis?
10
votes
1answer
163 views
NLOGTIME versus $\exists$DLOGTIME
$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have ...
12
votes
0answers
323 views
NP complete problem help
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
2
votes
0answers
60 views
Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm
I know the canonical way to show APX-Complete is to give an L-reduction from an already-known APX-complete problem. If I have used gap-preserving reduction to show a problem cannot be approximated ...
2
votes
1answer
137 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
320 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
116 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
59 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
78 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
82 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
87 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
136 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
110 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
140 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
119 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
123 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
263 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
170 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
122 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
280 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
99 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
148 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
92 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
173 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).
...
10
votes
1answer
170 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
53 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 ^{...
5
votes
0answers
97 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....
6
votes
1answer
296 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/...
2
votes
1answer
148 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
