# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

3,006 questions
Filter by
Sorted by
Tagged with
75 views

### Why is showing lower bounds for AM communication complexity difficult?

One of the major open problems in communication complexity is to show interesting lower bounds for the Arthur-Merlin (AM) communication complexity of some natural problems (i.e., lower bounds of the ...
207 views

### Is it known that P $\neq$ NP implies BQP $\neq$ NP?

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
797 views

### Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for ...
70 views

### Exchange cards with sum requirement

Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
41 views

### Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?

The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here: Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$: If $x \in L$ (...
1 vote
67 views

### What complexity class is characterized by having PSPACE verifiers?

Inspired by the 2 definitions (theorems) I am aware of, that are as follows. A language L belongs to QMA if there exists a BQP verifier V. A language L belongs to NP if there exists a P verifier V. ...
25 views

### NP-hard problem between two disjoint points

I have $n$ white points, $m$ black points, and $k$ blue points. Each blue point (i.e., variable) can have a value of 1 or -1. Each blue point can connect a maximum of $c$ edges to white and black ...
262 views

### Problems complete for non-deterministic PSPACE

Savitch's theorem, i.e. the fact that $NSPACE(f(n)^2) \subseteq DSPACE(f(n)^2)$ implies PSPACE = NPSPACE. Using the idea of Savitch, Sipser proves in his lectures that TQBF is PSPACE-complete. What ...
1 vote
62 views

### Generalization of the Hamiltonian path problem on Grid Graphs

Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$. Define the following ...
152 views

98 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 ...
55 views

### Is there a construction which multiplies and adds spanning trees in Logspace?

I.1 Suppose we have two planar graphs $G_1$ and $G_2$ with spanning tree count $C_1$ and $C_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G_1$ and $G_2$ ...
288 views

### Is Bayes optimal RL of a finite set of DFAs feasible?

Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set ...
737 views

### What is the complexity of (possibly succinct) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid which is to be filled with on/off values for each cell, with each number ...
66 views

### Sizes of tableau in PH

When one proves that SAT is NP-complete, one uses a tableau of size $n^k \times n^k$. Similarly, when one proves that TQBF is PSPACE-complete one uses a tableau of size $2^{n^k} \times n^k$. Thus, I'm ...
305 views

### Structural Complexity Theory References

I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory. As an undergraduate, I completed an independent reading ...
55 views

### complexity of the maximum rank correlation

Given two sets of vectors of dimension $p$, $x_1,\ldots,x_m$ and $y_1,\ldots,y_n$, The Maximum Rank Correlation estimator is the vector $\beta$ given by \arg\max_{b\in\mathbb{R}^p}\sum_{i=1}^m\sum_{...
58 views

### Complexity of maximum k-edge-colorable subgraph of a bipartite graph

Can the maximum $k$-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum $k$-colorable subgraph of the line graph of a bipartite graph be found in ...
1 vote
100 views

### Name and complexity of a stone placement puzzle

Consider the puzzle comprised of $N$ stones. Each stone is given a set of candidate locations. The goal is to put each stone in one of its candidate locations such that no two stones are put in the ...
1 vote
81 views

### Complexity of n-rooks completion

I am motivated by the post, Complexity of n-queens-completion. I am interested in completion problem of non-attacking rooks on a chessboard. Input: Given a chessboard of size $n*n$ with $n-k$ rooks ...
1k views

### Space alternating hierarchy

It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions). In the same paper, Immerman state that the ...
228 views

### Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, ...
328 views

Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{... 12 votes 1 answer 2k views ### Is the 3-coloring problem NP-hard on graphs of maximal degree 3? Consider the 3-coloring problem: given an undirected graph$G = (V, E)$, decide if there is a 3-coloring of$G$, i.e., a function$f$from$G$to$\{1, 2, 3\}$such that there is no edge$\{u, v\}$in ... 1 vote 0 answers 71 views ### Using a certificate in the proof of NP hardness Say I wanted to determine that the problem of membership in some language$L \subseteq \{0, 1\}^*$is NP-hard. Say that I have a reduction$r: \{\text{set of quantifier free formulas} \rightarrow \{0,...
It is known that $\text{NC} \neq \text{PSPACE}$, now I am wondering if there is a similar separation for $\text{QNC}$, the class of decision problems solvable by polylogarithmic-depth quantum circuits ...