Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,814
questions
0
votes
1answer
102 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 ...
-8
votes
0answers
61 views
Does this sequence of quantified boolean formulas make sense to anyone else? most of these qbfs are valid [closed]
do all logicians on earth know that a question is a qbf? yes
and they know the answer to a qbf is always yes or no? yes
ok good
all logicians know that solving one qbf is hard and buggy? yes
but ...
5
votes
0answers
71 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 ...
2
votes
0answers
85 views
+100
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$ ...
6
votes
1answer
253 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 ...
-1
votes
0answers
68 views
How exactly does derandomization of BPP imply lower bounds on NEXP
In their paper Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds, Kabanets and Impagliazzo prove that if $BPP=P$ then either $(i) NEXP \nsubseteq P_{/poly}$ or $(ii)$ ...
0
votes
1answer
92 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
53 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 ...
-4
votes
0answers
37 views
Research regarding human vs algorithm on NP-hard problems
I am interested in the comparison of human performance vs algorithmic performance on NP-hard problems, both with regard to exact solutions and approximations, with the intent to find areas where ...
-1
votes
1answer
83 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
100 views
A query regarding relation b/w complexity classes $NP$ and $BQP$ in case of collapse of $PH$?
Assuming if $PSPACE$ collapses to the class $NP^{NP}$ $\mathsf{\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P = PSPACE}$.
Since $\mathsf{NP\subseteq NP^{NP}}$ and $\mathsf{BQP\subseteq QMA \subseteq PSPACE} \...
2
votes
0answers
95 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
153 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)...
8
votes
1answer
214 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
71 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
148 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
147 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 ...
4
votes
2answers
224 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
135 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
95 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
46 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
122 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
152 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
72 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
222 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
121 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 ...
6
votes
1answer
278 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
54 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
222 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
103 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
226 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
189 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
195 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
70 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
402 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
52 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
101 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 ...
0
votes
0answers
79 views
Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$
Crossposted at MathOverflow
A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$. $\mathbf{1}$ is ...
1
vote
0answers
199 views
An $O(n^2\log^c{n})$ algorithm for matrix multiplication in this paper?
In the newest version of this paper by Yijie Han, the author claims that matrix multiplication can be solved by an $\tilde{O}(n^2)$ algorithm. It should be a big result, but it is still in arxiv and ...
3
votes
1answer
255 views
Proof and computational complexity
I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...
4
votes
1answer
214 views
Complexity of relaxed edge colouring
A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are ...
1
vote
1answer
148 views
KRW Conjecture: separation of NC^1 and P
More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more ...
0
votes
1answer
70 views
Given a partition and an element, find the subset that includes this element
I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
1
vote
0answers
203 views
anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
3
votes
0answers
98 views
Monomial Sparsity of Boolean Functions
Suppose you have some boolean function $f: \{-1,1\}^n \rightarrow \{-1,1\}$ with rational coefficients such that all degree 1 monomials of $f$ have a nonzero coefficient and the degree $n$ monomial ...
0
votes
0answers
48 views
Complexity of finding typing derivation trees
In type theories where type checking is decidable do we have estimates for how much time/space it takes to find a typing derivation tree of a valid typing judgment? Do any published references do this ...
4
votes
1answer
366 views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.
...
4
votes
3answers
151 views
The complexity of LH with constant gap
Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue ...
1
vote
0answers
66 views
Additive error approximations of GapP functions
Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that
\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}
Consider a ...