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