Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,822
questions
0
votes
0answers
3 views
Expert Opinion on the Importance of Polynomial Hierarchy Collapse
$P\ vs\ NP$ and $NP\ vs\ co-NP$ are perhaps the two central questions in TCS and Complexity Theory with numerous surveys devoted to these problems.
But (relatively) not much has been discussed ...
0
votes
0answers
73 views
Computational complexity of Private Computation
In a recent work (Sun2017), Sun and Jafar defined the Private Computation (PC) problem where a user wants to compute a function of $K$ datasets, using $N$ distributed and non-colluding servers, ...
9
votes
2answers
755 views
Randomized algorithms not based on Schwartz-Zippel
Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
0
votes
0answers
34 views
Query in the proof of greedy manipulation theorem (of a voting scheme)
Paper being referred to: http://www.cs.cmu.edu/~arielpro/15896/docs/paper9.pdf (The Computational Difficulty of Manipulating an Election).
I have a query in Theorem 1 of this paper; specifically, in ...
1
vote
0answers
48 views
Natural problems believed to be in EQP but not BPP
Are there any “natural” problems in $\mathsf{EQP}$ that are believed to not be in $\mathsf{BPP}$? If so, what are some exapmles?
4
votes
1answer
214 views
Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?
Some classes, such as ALL, ELEMENTARY, and R, are very badly behaved when used as oracles. For instance, all three of these classes trivially collapse P and EXP, even though (by the Time Hierarchy ...
3
votes
0answers
131 views
Is it possible that the Aanderaa–Karp–Rosenberg conjecture is just a bit false?
The Aanderaa–Karp–Rosenberg conjecture is that any non-trivial monotone property on graphs is evasive. It has been proved for several special cases, but for a general graph on $n$ vertices, we only ...
3
votes
0answers
107 views
Detailed proof of Theorem 2.1 in Papadimitrou book (Multitape TM to SingleTape TM)
I want to know if anybody knows a detailed proof of Theorem 2.1 of Papadimitrou's book Computational Complexity. The theorem states "Given any $k$-string Turing machine $M$ operating within time $...
10
votes
0answers
121 views
Fastest Known Algorithm to Count Acyclic Orientations in a Graph
Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....
0
votes
0answers
25 views
Can we pick a basis for synchronous circuits which coarsens towards the target partition at every layer?
Given a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ and a Boolean basis for circuit gates $B$ (for instance $B = \{AND, OR\}$), we can construct the set of size optimal synchronous (Harper ...
1
vote
0answers
55 views
A reduction from the maximum $k$-closure problem to the clique problem
Fix a partially ordered set $(P, \le)$ with $N$ elements and real weights $w(p)$ for each $p \in P$. A subset $S \subset P$ is called closed if for any $x, y$ with $y \in S$ and $x \le y$ we also ...
0
votes
0answers
78 views
Query about P/poly and Polynomial Hierarchy Collapse to $\Sigma _{2}$
I am not conversant in the complexity class $P/poly$. While reading about the class on wiki I encountered two conditional statements about it, namely:
If $NP ⊆ P/poly$ then $PH$ (the polynomial ...
4
votes
0answers
152 views
Computational Complexity of 3SAT variant with additional restrictions on variables/clauses
Given a 3SAT problem with the additional constraints that:
No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses.
For any/every clause, the ...
2
votes
1answer
164 views
An easy computable injection with a hard inverse
I was reading Charles Bennett's Thermodynamics of Computer Science and a passage (p. 926) caught my eye
The construction of a reversible machine from an irreversible machine implies that the open ...
4
votes
0answers
120 views
Computational Complexity of MIN-EQ-3-CNF
Consider the decision problem:
MIN-EQ-CNF= $\{\langle\phi, k\rangle |\exists \text{CNF formula } \psi \text{ of size }\leq k\text{ that is equivalent to the CNF formula }\phi\}$
CNF is a Boolean ...
2
votes
0answers
84 views
Recovering the inputs to Boolean circuits after partial evaluation
This question discusses Boolean Circuits and Boolean functions from $n>1$ inputs to one Boolean output. Notation: $\textit{arity}(\mathcal{C})=n$ if $\mathcal{C}$ takes $n$ inputs, similarly for ...
0
votes
1answer
112 views
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Modifying following TedP
We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
5
votes
0answers
83 views
Fine-Grained Hardness for Undirected Hamiltonicity
The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time.
However, for undirected graphs on $n$ nodes, there is an ...
3
votes
0answers
103 views
Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover
Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
7
votes
1answer
291 views
Cook inspiration for NP completeness
An academic descendant of Cook just lectured on NP completeness. He said that the idea came from a well-known theorem in first-order logic that talks about completeness of satisfiability for ...
0
votes
1answer
97 views
Diophantine equations with bounds on variables
Solving Diophantine equations is famously known to be undecidable. What about Diophantine equations to be solved over a finite domain? In particular, if I put an upper bound $k$ over the value of the ...
0
votes
0answers
59 views
EXPSPACE-complete problems involving numbers
This is a subset of this question. I'm looking for EXPSPACE-complete problems, for using in a reduction, which involve numbers in some ways, since my target problem involves numbers and linear ...
-1
votes
1answer
87 views
Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?
I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization.
If instead we are given a partial truth table, and we just ...
2
votes
0answers
103 views
Asymptotic complexity lower bounds of proof checking
This paper on universal search mentions (on pp. 6-7) that proof checking can be done in $O(n^2)$ where $n$ is the length of the proof. Is this optimal? I don't want to specify the problem too ...
3
votes
1answer
157 views
complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)
The fermionant is a matrix function from physics, which is indexed by a positive integer $k$:
\begin{align}
\operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
9
votes
1answer
241 views
Does Horn SAT (Horn formula in CNF) have an integral polytope?
In some ways, my question is related to this: Is the matching polytope integral?
Matching and Horn-SAT are both polynomial time solvable.. So I wonder if there is a Horn polytope, similar to the ...
0
votes
0answers
79 views
Useful primitives CPUs could provide, from TC0 (or NC1)
I just listened to XYZ talking about "How Universal Is the Idea of Numbers?", and bashing the concept as an accidental historical artifact. He suggested that totally different computational ...
2
votes
1answer
214 views
3SAT to 1-in-3SAT reduction with additonal constraints
The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:
For each 3SAT clause: $x+y+z=1$
Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses:
$R(...
1
vote
0answers
148 views
Is polynomial-time the same in all classical computational models?
There are many models of computability, all giving the same notion of 'computable function'. To pick a few examples:
Turing machines (with variants: one-ended, two-ended, multiple tapes...)
RAM ...
5
votes
2answers
256 views
Complexity of "can we get a cycle by stacking directed bipartite graphs?"
Preliminaries
We consider directed bipartite graphs of the form $G = (V,V',E)$, in which the nodes are partitioned into $V = \{1,\ldots,n\}$ and $V'=\{1',\ldots,n'\}$, with $|V|=|V'|=n$, and $E\...
1
vote
1answer
136 views
Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
0
votes
0answers
104 views
Questions about the equivalence between PH and depth-d circuits with respect to an oracle
Consider an oracle $A$ and the language
\begin{equation}
P(A) = \{x\in \{0, 1\}^{n}: \text{the number of strings in }~A~\text{of length}~|x|~\text{is odd}\}.
\end{equation}
I am trying to make sense ...
1
vote
1answer
48 views
Graph classes where giving a q-clique edge cover makes testing for q-colouring easy
A $q$-clique of a graph is a complete subgraph on $q$ vertices.
A $q$-clique edge cover of $G$ is a set of subgraphs of $G$ such that each subgraph is a $q$-clique and each edge of G is contained in ...
4
votes
0answers
127 views
An NP-hard Hidden Subgroup Problem
I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (https://en.wikipedia.org/wiki/Hidden_subgroup_problem), but that doesn't quite meet the standard problem's ...
2
votes
1answer
184 views
Minimum cut with size bounds $k\leq |S| \leq |V|-k$
It is known by the max flow min cut theorem that the minimum cut problem is in $P$.
I am interested in knowing what is known on the complexity of the minimum cut with size $k\leq |S| \leq , |V|- k$. ...
2
votes
0answers
79 views
Result showing that DTIME[T] is strictly contained in random-access NTIME[T]
I recall seeing a result showing that multi-tape DTIME[T] is strictly contained in random-access NTIME[T] for reasonably large T (so not the PPST proof with the $\log^\star$ sort of factors), but I ...
1
vote
0answers
73 views
Parametrization of context-sensitive language in polynomial time
Let $\Sigma$ be a finite alphabet. Let $L\subset \Sigma^*$ be a context-sensitive language containing a word of every length.
Can we always find $f:\Sigma^*\to L$ computable in polynomial time in ...
5
votes
0answers
229 views
$\#$P hardness of computing weighted sum of degree $2$ polynomials
Consider polynomials $f: \{0, 1\}^{n} \rightarrow \{0, 1\}$ over $\mathbb{F}_2$ (addition and multiplication are taken modulo $2$.) Consider integers $x \in \{0,1\}^{n}$, written in binary. Let $\...
2
votes
3answers
127 views
Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy
Let there be a set of $P$ polynomial equations $f_j(x_1,x_2...x_V)=0$ where $1\leq j\leq P$. For each $f_j$ the coefficients are real and every variable goes up to degree $D$. It is also guaranteed ...
7
votes
1answer
282 views
Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries
My question concerns the NP-hardness of the following discrete optimization problem:
Given a matrix $A \in \{ \pm 1 \}^{m\times n}$,
$$\begin{array}{ll} \underset{x \in \{ \pm 1 \}^m ,\, y \in \{ \pm ...
-2
votes
1answer
61 views
Is time-slot matchmaking NP-hard?
I have the following problem, which I intuitively expect to be NP-hard but cannot see how to write a reduction for:
Givens: There is a fixed set of time slots, e.g. {9-10, 10-11, 11-12, 12-1, etc.}. ...
7
votes
0answers
225 views
How is a "low-degree polynomial" precisely defined in Algebrization?
I'm going through papers which present algebrization as a barrier and I'm trying to understand how "low-degree" polynomials are precisely defined, i.e. are they low with respect to the ...
3
votes
0answers
107 views
Complete problems for $(NP\cap CoNP)/poly$ class and universal representations
It is conjectured that $NP\cap CoNP$ does not have a complete problem with respect to the polynomial-time many-to-one reductions. I would like to know the current knowledge about the nonuniform ...
3
votes
1answer
248 views
Are there two definitions of Cobham's thesis?
In wikipedia, Cobham's thesis (or Cobham-Edmonds thesis) states:
computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time
So ...
4
votes
0answers
191 views
What does width $4$ permutation branching program correspond to?
$L$ can be computed by a family of programs over $S_3$
of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of
polynomial size.
$L$ can be computed by a family ...
2
votes
0answers
199 views
Simultaneous evidence for $L\neq NL$ and $P\neq NP$
We believe $L\neq NL$ and $P\neq NP$.
Is there any evidence which simultaneously imply $L\neq NL$ and $P\neq NP$?
3
votes
0answers
76 views
Useful notion of ambiguous growing context-sensitive language
As far as I understand there is no useful notion of ambiguous context-sensitive language.
For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
2
votes
0answers
403 views
The implication of $ S(SAT)=2^{\Omega{(n)}} $ Conjecture (5.7 in Wigderson Book)
I started to read Avi Wigderson book Math and Computation, which get me excited about the following:
Conjecture 5.7. $
S(SAT)=2^{\Omega{(n)}}
$,
where $S$ denotes the size of the smallest Boolean ...
2
votes
1answer
59 views
Relative error estimation of a special type of GapP function
Consider the functions included in the complexity class GapP.
We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly ...
3
votes
1answer
106 views
Hardness when restricted to an infinite number of far apart instance sizes
Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance ...
