# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,529 questions
38 views

### How to efficiently verify if a semantic symmetry of a CNF formula is valid?

It is easy to verify that a syntactic symmetry of a CNF formula is correct. Is it also possible to check in polynomial time that a semantic symmetry which is not a syntactic symmetry of a formula is ...
252 views

### Non-Orthogonal Vectors Problem

Consider the following problems: Orthogonal Vectors Problem Input: A set $S$ of $n$ Boolean vectors each of length $d$. Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ ...
122 views

### Complexity of isotopy of embedded graphs

I am looking for previous work on the following problem: given two graphs embedded in the plane without crossing, determine if they are isotopic. By isotopic I mean that there is a continuous ...
94 views

227 views

### Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?
258 views

### Relationship of the P=PSPACE problem to alternating complexity classes

From a very naive point of view of someone who haven't studied complexity theory in depth, I am wondering whether the theorems that APSPACE=EXPTIME and AP=PSPACE have any derived results on separating ...
218 views

### Can we efficiently distinguish between P and BPP?

Let's say algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, $$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$...
111 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$ ...
1k views

### Deciding whether an interval contains a prime number

What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
131 views

### Max cut problem between two connected subgraphs

Let $G$ be a connected graph. Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known ...
62 views

### Restricted Universe Exact Cover

Apologies for a simple question - I am a beginning graduate student in TCS. Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and ...
37 views

### Min cut problem on unbalanced partitions for planar graphs with unit capacity edges

The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$...
187 views

### How “hard” is it to maximize a polynomial function subject to linear constraints?

General Problem Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
122 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 ...
173 views

### What is consequence of $PH\subseteq NSPACE((\log n)^2)$?

What is consequences of $PH\subseteq NSPACE((\log n)^2)$? We don't even know PH is equals to L or not. I am wondering what will be happened when $PH\subseteq NSPACE((\log n)^2)$?
115 views

### Average-case analogue of Small-bias Spaces

Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias | \mathbb{E}_{x \in S} [ (-...
129 views

### What does “hold uniformly” mean in the context of asymptotic analysis?

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):
82 views

### Critical Assignments vs Read-Once Branching Programs - Reference Request

Straight to the point: I'm looking for a reference for the fact that the complexity of a read-once branching program solving the search problem for an unsatisfiable formula $F$ is at least the ...
180 views

### Are there any known functions in NC2 but not in TC1?

Uniform TC1 is known to be in Catalytic Logspace. To improve the lower bound, we are looking for some functions known to be in NC2 but not in TC1. Also, what are some of the natural functions known ...
259 views

### Nondeterminism is on average useless for circuits?

Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result. Theorem[SW98]: For every constant $k>1$, almost all boolean functions with ...
89 views

### An explicit hard function for P/poly

It is known that $\textbf{MA}_{\textbf{EXP}} \not\subset \textbf{P/poly}$. Is it known any explicit language from $\textbf{MA}_{\textbf{EXP}}$ that does not belongs to $\textbf{P/poly}$? (An example ...
56 views

### How to make any graph 2-degenerate?

I have to show a PPT(polynomial time reduction) from 'Colorful graph Motif' to '2-Degenerate Steiner Tree'. As input graph should be 2-degenerate, but here is normal graph G (that is, basically an ...