Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

590 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
193 views

Non-uniform average-case complexity of NP

It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
5
votes
0answers
304 views

Sparse Boolean Function and Other Boolean Functions

Let $s$ be a Sparse boolean function $s:\{0,1\}^{n}\rightarrow \{0,1\}$ such that $|s^{-1}(1)| \leq 2^{n\delta}, 0 < \delta <1$ The majority function $MAJ_{n}$ takes value 1 if and only if the ...
5
votes
0answers
763 views

Does L=P imply any new complexity class separations?

If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L. I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly ...
5
votes
0answers
1k views

Bounded Post Correspondence Problem NP-Complete Proof

I'm looking for a simple proof that shows that the Bounded-PCP problem belongs to NP-Complete as many text books say so. It is clear to me that the problem is decidable but I cannot find any reduction ...
5
votes
0answers
190 views

Reduction from planar bounded NCL to a static puzzle game

I call Fill3 the following simple game: the input is a $n \times n$ grid; every cell of the grid has a type: OR, AND, CHOICE, FANOUT and FIXED and can be rotated 0,...
5
votes
0answers
132 views

Succinct graphs with ability to perform random walk

Suppose I have an exponentially large graph $G$ ($|G|=2^n$) supplied with an efficient (of size $poly(n)$) randomized circuit $C_G$ implementing the random walk on $G$ - that is, $C_G$ takes a vertex ...
5
votes
0answers
133 views

What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?

The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions. Since $\mathsf{...
5
votes
0answers
191 views

Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC. My question is, can we do better for planar graphs? It is ...
5
votes
0answers
193 views

Logic capturing automorphism-invariant $\mathsf{AC^0}$ properties

Q1. Is there a logic that is computable in polynomial-time which contains all order-invariant properties computable in smaller classes like $\mathsf{AC^0}$ (or $\mathsf{TC^0}$)? Motivation As you ...
5
votes
0answers
326 views

Complexity of balanced graph partition problem

Wagner and Wagner, in "Between min cut and graph bisection" (MFCS 1993), studied a variant of minimum bisection problem where we seek a cut with minimum size such that each partition has at least $\...
5
votes
0answers
204 views

Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?

If I understand this correctly, arithmetizating a formula is a way of "interpolating" a polynomial in such a way that polynomial evaluated on 0's and 1's corresponds to "unsatisfiable" if it is a root,...
5
votes
1answer
1k views

Optimality of Greedy algorithm for minimization Knapsack Problem

Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized. The greedy ...
4
votes
0answers
238 views

Difficulty of graph coloring and independent set?

Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable. Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
4
votes
0answers
185 views

Testing emptiness property complexity in Sum of Squares Proof systems

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
4
votes
0answers
72 views

Refinement of the hierarchy theorem of a complexity class

Say $\mathrm{CTIME}$ is some complexity measure, syntactic or semantic (e.g. $\mathrm{DTIME}$ or $\mathrm{BPTIME}$). If we already know that for some $f(n) = \omega(n)$, $\mathrm{CTIME}(n) \subsetneq \...
4
votes
0answers
82 views

Fixed dimension Linear Integer Programming in $NC$

We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
4
votes
0answers
110 views

Asymptotic complexity of mass production

For a function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, let $C(f)$ be the circuit complexity (for concreteness, constants and NOT gates are free, while 2-input AND gates cost 1). Let $k{\times}f : \{0,1\}...
4
votes
0answers
114 views

A variant of hitting set: finding a matching to hit all edge sets

In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ ...
4
votes
0answers
147 views

Simulate a heap in linear time

Is there anything in the literature on the following problem?: Take a sequence of operations of Insert(element) and PopMin and ...
4
votes
0answers
77 views

Circuits computing functions of inputs smaller than $n$

The usual circuit complexity concerns circuits where circuit $C_n$ computes function $f_n$. I am interested in circuits such that $C_n$ can compute $f_i$ for all $i \leq n$. I am assuming that the ...
4
votes
0answers
76 views

2-hop distributed coloring in the CONGEST model

Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$. A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
4
votes
0answers
141 views

Formalization of proofs and CC paradox? - Part II

This was the second part of my previous question. It is very similar, and probably it has a similar answer (as Emil said in a comment), but I thought it was worth to separate it and ask it as a new ...
4
votes
0answers
65 views

Complexity of comparing polygon perimeters

The problem of comparing the lengths of two paths of line segments connecting points in $\mathbb{Q}^2$ is not known to be in $\text{P}$, nor even in $\text{NP}$. Does requiring that the paths begin ...
4
votes
0answers
124 views

Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$

The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests ...
4
votes
0answers
70 views

Computational Complexity of the Helpmate problem in Chess

It is well known that Chess is EXPTIME-Complete. I am interested in the related "Helpmate" problem. Given an $N$ by $N$ chessboard, is there any sequence of at most $k$ moves that leads to Black's ...
4
votes
0answers
188 views

Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$. For more info, see "Superpolynomial circuits, almost sparse oracles ...
4
votes
0answers
182 views

What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

We know that Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable,so what is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$? Is it equivalent to Tarski elimination ...
4
votes
0answers
362 views

What happens when PSPACE contains NEXP?

The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial). In the ...
4
votes
0answers
167 views

Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular ...
4
votes
0answers
185 views

What exactly did Lenstra prove on mixed integer linear program?

I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
4
votes
0answers
87 views

A succinct version of permanent that is $EXP$-complete

Succinct version of permanent is $NEXP$-hard (https://eccc.weizmann.ac.il/report/2012/086/) and so unlikely to be $EXP$-complete. Permanent mod $2$ is in $\oplus L$ and so succinct version is ...
4
votes
0answers
146 views

On status of Valiant's $NC^2=P^{\#P}$ provability program?

In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back. What is the rationale (at ...
4
votes
0answers
135 views

About counting the “total size” of non-zero Fourier coefficients of a Boolean function

Given a $f: \{-1,1\}^n \rightarrow \mathbb{R}$, I want to compute this quantity, $\sum_{ \hat{f}(S) \neq 0, S \subseteq 2^{[n]}} \vert S \vert $ i.e the sum of the sizes of the subsets of $[n]$ ...
4
votes
0answers
195 views

Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in ...
4
votes
0answers
147 views

Can coNLogTime verification be used instead of PTime verification when characterising NP?

I recently read a paper that presented a proof calculus where the verification of whether a given proof is valid was NL-complete. The authors apparently decided that the checking procedure was not ...
4
votes
0answers
84 views

Fixed-parameter tractability of string homomorphism

String homomorphism is a function $h: \Sigma \to \Sigma^*$, which naturally defines a homomorphism on strings from $\Sigma^*$ with respect to concatenation. We denote $H(s) = h(s_1)h(s_2)\dots h(s_n)$ ...
4
votes
0answers
169 views

NP-completeness of a specific topological sorting problem

Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a ...
4
votes
0answers
126 views

Is there a certificate definition for polyL?

Arora explained in his book a certificate definition for $\mathsf{NL}$ using a read-once tape. Can we apply a similar definition for the class $\mathsf{polyL}$?
4
votes
0answers
136 views

Computing Minima of the Projection of a Binary Cube

The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-...
4
votes
0answers
100 views

$\text{P}^{\text{Mod}_k\text{P}}$ vs $\text{P}^{\#\text{P}}$?

$\text{Mod}_k\text{P}$ is the class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no." For constant $k$, one ...
4
votes
0answers
101 views

$\mathsf{P}$ is the closure of [finite set] under [operation between languages]

I am searching for statements of the above form, that is, asserting the existence of a finite set $F$ of languages and one or more operations $\otimes\colon \mathcal{P}(\Sigma^*) \times \mathcal{P}(\...
4
votes
0answers
180 views

Graph Isomorphism of Strongly Regular Graph with fixed parameter

$G, H$ are strongly regular graphs with parameter $(n, r, \lambda, \mu)$ where $\lambda$ is constant. Here, $n$ is the number of total vertices. Each graph is $r$ regular. Every two adjacent ...
4
votes
0answers
66 views

Combinatorial characterization of hypergraph Tseitin satisfiability

The Tseitin formulas are as follows: Given a connected graph and a function $\alpha: V \rightarrow \{0,1\}$. Associate each edge $e$ with a variable $x_e$. The Tseitin formula $G(\alpha)$ is defined ...
4
votes
0answers
122 views

Lower Bound for Nonzero Terms of a Polynomial Fully Sensitive at 0

Every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be uniquely represented as a multilinear polynomial $p=\sum_{S\subseteq [n]}c_S \chi_s$ where $\chi_s=\prod_{i\in S}x_i$. A boolean function is ...
4
votes
0answers
243 views

Possibility of weaker forms of $P = NP$

Assuming that $P \ne NP$ how surprising would it be if a weaker form of $P = NP$ holds? For example consider the following weaker forms of $P = NP$: $NP \subseteq DTime(2^{O(n^\varepsilon)})$ for ...
4
votes
0answers
112 views

When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?

I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of Papadimitriou's textbook. We are in the function-problem world. The problem ...
4
votes
0answers
230 views

Bit complexity of modulo operations?

We know that using FFT we can compute multiplication of an $a$ bit number with a $b$ bit number in $(a+b)^{1+\epsilon}$ time. My question is supposing we want to compute $A\bmod B$ where $A$ is an $a=...
4
votes
0answers
191 views

A SAT related question

Given a sequence of $n$ propositional formulas $\varphi_1, \cdots, \varphi_n$, a propositional formula $\phi$, a number $1\leq \theta\leq n$. Define $K=\min\{k\mid \wedge_{i=k}^n \varphi_i\not\models ...
4
votes
0answers
107 views

Rigid families of $\{0,1\}$ matrices

We know that there are many families of matrices over $\Bbb F_q$, $\Bbb R$ etc are rigid. See http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf Do we know there are many families of rigid REAL ...
4
votes
0answers
128 views

Can we decide Red-blue cut problem in polynomial time?

Given a directed graph whose arcs are coloured red and blue and integers $r$ and $b$, can we decide in polynomial time whether the digraph has a cut with at most $r$ red arcs and at most $b$ blue arcs?...