# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

599 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
108 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 ...
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?...
146 views

### Recognition problem of cycle permutation graphs

A cycle permutation graph is a cubic graph composed from two $n$-cycles each labeled $1, 2,..., n$, with additional edges connecting vertex $i$ in the first cycle to vertex $\pi(i)$ in the second, ...
167 views

### Problems in dynamic algorithms in computational geometry

The publication of Chiang and Tamassia's paper on dynamic algorithms in computational geometry included several algorithms used in solving dynamic computational geometry problems such as: Dynamic ...
247 views

### Is there a reason we haven't been able to prove that the existence of natural NPI problems even conditionally under assumption NPI is not empty?

We can write ${\mathsf {NP}}-{\mathsf P}= {\mathsf {NPC}}\cup {\mathsf {NPI}}$ where ${\mathsf {NPC}}$ is the set of ${\mathsf {NP}}$-complete languages (not in ${\mathsf {P}}$ by this partition), ...
75 views

### How many exponentiations can the Shamir algorithm reduce?

The Shamir's algorithm is depicted as follows (cited from Handbook of Applied Cryptography, chapter 14, algorithm 14.88, page 618) Shamir's algorithm INPUT: group elements $g_0,g_1,\dots, g_{k-1}$ ...
241 views

### Notion of associativity for ternary relations?

Consider the problem $\def\GEN{\mathrm{GEN}}\GEN$: given a ternary relation $R \subseteq X^3$ and a subset $S \subseteq X$, is the closure of $S$ with respect to $R$ equal to the whole set $X$? By ...
114 views

382 views

### The number of maximal subsets with sum less than $m$

I've met this problem. I would like to know to which complexity class it belongs. Input a set of positive integers $I$, an integer $m$, an integer $n$. Question Is the number of $S \subseteq I$ ...
149 views

### Vertex Covers whose vertex induced subgraph has an even number of edges and no isolated vertices

Let $G$ be a graph, and let $C_{E,0}$ be the number of those vertex covers of $G$ satisfying both the following properties: Their corresponding vertex induced subgraph has an even number of edges. ...
327 views

### What does “no integrality gap” imply?

I'm currently working on a linear time heuristic for the rectangle decomposition of a binary matrix. This problem has a polynomial time solution, which in our case is too slow for large-scale ...
97 views

### What is the query and randomness complexity for very efficient PCPs?

In the 2012 paper On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs, the authors state the following (paraphrased from page 11). Theorem 1 (informal). There is a PCP system ...
601 views

### Nondeterministic linear time vs. the deterministic time hierarchy

How much is known about nondeterministic linear time? I'm aware that $$\mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$ Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$? ...
224 views

327 views

260 views

### Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two

It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with ...
275 views

### What is the complexity of #satisfiable instances of k-SAT ?

To continue the question posted by user1749 on Oct 13 2010 : How many instances of 3-SAT are satisfiable? Which was: Consider the 3-SAT problem on n variables. The number of possible distinct ...
209 views

### Complexity of Max Bisection on cubic planar graphs?

Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximum. Max Bisection is $NP$-complete on cubic graphs and also on planar ...
334 views

### Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

$CFL$ is the class of context-free languages. Question Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $DCFL$?
88 views

### Isomorphic subforest problem

I recently read that the following problem is NP-Complete: Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$? The reference provide was to the textbook “Computers and ...
115 views

### Matrix multiplication when one matrix is fixed

Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry One is allowed to pre-process this matrix as appropriate. Given another positive integer entried $B$...
71 views

### Example of a hardness-of-approximation proof which improves the approximation factor?

Are there any examples of hardness-of-approximation reductions where we get a better hardness bound for the problem we've reduced to than the problem we've reduced from? In the examples I've seen so ...