# 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
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
133 views

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,...
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 ...
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-...
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 ...
72 views

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$ ...
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 ...
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 ...
76 views

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 ...
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 ...
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 ...
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 ...
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 ...
230 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 ...
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?...