# Questions tagged [computational-complexity]

This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

1,161 questions
Filter by
Sorted by
Tagged with
11 views

### Partition of multisets of polynomials

Problem: Given a multiset $S$ of irreducible polynomials in $\mathbb{Z}[x]$, say YES if $S$ can be partitioned into two nonempty multisets $A$ and $B$ such that both the product of all the elements of ...
417 views

### Would efficient factoring have any *other* useful applications?

This question is certainly somewhat opinion-based, but hopefully not hopelessly so. The granddaddy of all applications for an efficient period finding or factoring capability (e.g. Shor's algorithm) ...
97 views

107 views

### Complexity of games with graph classes

Let $\mathfrak{G}$ be the class of all finite directed and undirected graphs. Let $A,B\subseteq \mathfrak{G}$, $A$ and $B$ are closed under graph isomorphisms, and $A \cap B = \varnothing$. Consider ...
72 views

### 3-SAT family with $\omega(n^2)$ time complexity

A 3-SAT family is an algorithm that given a positive integer $n$ outputs a 3-SAT problem in $n$ clauses in $O(n^{1+\epsilon})$ time ($\epsilon$ is to allow for the indexing of the variables). A ...
36 views

### Reduce a recursively enumerable set to a recursive one not too sparsely

Fix a real $1<\epsilon<2$. Suppose we have a recursively enumerable set $S\subset \mathbb{N}$ with a specific program halting on it. Then denote by $\mathrm{time}_S(x)$ the time it takes for the ...
101 views

5k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
122 views

### Counting $\mathrm{mod}\:p$ solutions of Diophantine equation in two variables taking $O(p^2)$ time

Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time? Geometrically this means we have to sort through a positive proportion of the ...
65 views

### Is minimum weight vertex cover problem NP-easy? [closed]

I think that Minimum weight vertex cover problem is NP-easy. However I don't know how to prove that. Does anyone know how to prove it?
22 views

### Can it be decided in advance if the relaxed (non-integer) solution of a integer program will result in low error when rounded?

Is there any useful characterization of the class of integer programs where rounding of the relaxed (non-integer) solution will provably result in a good approximation of the minimum of the objective ...
135 views

### Is it intractable to locate a sequence of prime/not-prime bits?

For $n \in \mathbb{N}$, Let $p(n) = 1$ if $n$ is prime and $p(n) = 0$ otherwise. Roughly, my question is Rough question: Given a rough estimate of $n$ and a sequence $p(n), p(n+1), \ldots, p(n+k-1)$ ...
290 views

### Complexity of rectangular matrix multiplication

I am interested in the complexity of multiplying two matrices $A$ and $B$, i.e. to compute $AB$. From [Le Gall and Urrotia], I know that: if $A$ and $B$ are square-matrices of size $n$, then this can ...
46 views

### Literature about graph isomorphism and incidence matrix [closed]

I would like to read some paper, if any, for some classes of graphs, regarding inverting (right/left inverting) the incidence matrix to solve the graph isomorphism problem. Or anyway some known facts ...
2k views

### Complete problems for randomized complexity classes

It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for a suitable oracle $O$ it is believed not to have complete problems, unless P=BPP. I wonder if the class MA (the randomized ...
136 views

### How to decide if an algebraic number is a root of a given polynomial?

Let $p$ be a polynomial with rational coefficients and $\alpha = \sqrt[n]{q}e^{i2k\pi/m}$ for some natural numbers $n,m,k$ and a rational number $q > 0$. Is there an effective algorithm for ...
125 views

### Is factorial computation known to be in a class smaller than $FEXP$?

Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
121 views

### Maximum independent set in dense graphs

Let $0 < A < 1$ and $G$ be connected d-regular graph with degree $d=[A n]$. The density of $G$ is about $A$. Q1 Are there constraints on $A$ such that finding maximum independent set of $G$ is ...
674 views

### $\mathit{NP}$-hard statements which are $\mathit{NP}$-complete under the Riemann Hypothesis

$\newcommand\NP{\mathit{NP}}\newcommand\SAT{\mathit{SAT}}\newcommand\CH{\mathit{CH}}\newcommand\PSPACE{\mathit{PSPACE}}$Are there $\NP$-hard problems which are $\NP$-complete under the Riemann ...
66 views

### Efficient Algorithm to Find Subset of Vectors Over $\mathbb{F}_q$ Living in Low Dimensional Subspace

Let $q$ be a fixed prime, $P, Q$ be polynomials with $\mathrm{deg}(Q) < \mathrm{deg}(P)$ and $h = O(\log n)$. Let $S$ be a subset of $\mathbb{F}_q^n$ of size $P(n)$ such that there exists a subset ...
### Polynomial-time algorithm for uniformly sampling the $n$-slice of a context-free language
Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$. Is there a polynomial-time algorithm for uniformly sampling from ...