Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
57