# 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,153 questions
Filter by
Sorted by
Tagged with
43 views

I feel the following problem might be resolved already. But I could not find any related answers. If $p_1,p_2,\dots,p_t$ are primes where $2\leq t=o(\log n)$ is there a prime within $$\prod_{i=1}^... 2answers 2k views ### Kolmogorov complexity of classical music I have an impression that classical music pieces are more "structured" than white noise and more "complicated" than the soundtracks of the Billboard Hot 100 songs. So assuming we ... 0answers 66 views ### Minimum size of a Diophantine equation detecting the emptiness of a recursive set I have a program P taking an integer as input and outputting a Boolean value. It runs in polynomial time in the length of the input. There necessarily exists a Diophantine equation that has a ... 0answers 137 views ### Determine the minimal elements of a Dynkin system generated by a finite set of finite sets (This is a refined version of https://cs.stackexchange.com/q/144371) Let \Omega be a finite set. A Dynkin system on \Omega is a subset of the power set of \Omega containing \Omega, which is ... 3answers 674 views ### Undecidable infinite analogs of NP-complete problems? In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "... 1answer 124 views ### Computationally intractable orbit of a monoid action on a finite set Suppose for each integer n\geq 1 we have a submonoid M_n\subset \mathrm{Self}(\{1, \dots, n\}) of self-maps of \{1, \dots, n\}. A characterization of M_n is an algorithm that takes an integer ... 1answer 121 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 ... 1answer 61 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? 0answers 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 ... 1answer 133 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) ... 0answers 44 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 ... 2answers 257 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 ... 0answers 134 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 ... 1answer 123 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 ... 1answer 98 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 ... 0answers 117 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 ... 0answers 62 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 ... 1answer 667 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 ... 1answer 277 views ### What is the computational cost in a neural network? I have seen that some papers talk of computational cost of the network and they measure it in MACs. I didn't find any clear explanation of what it is. Could anyone explain in clear words the meaning ... 0answers 49 views ### 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 ... 0answers 429 views ### Langlands program and complexity theory Back when I was an undergraduate, I spent some time reading the about the modularity conjecture, but the details are fuzzy now. One of the motivations I imagined for the Langlands program was for ... 1answer 172 views ### What is this invariant graph? Let G be a simple graph (finite or infinite), [n]\mathrel{:=}\{1,...,n\}. Define the function:$$\varepsilon_n(G)\mathrel{:=}\min_\phi{\lvert{\operatorname{dom} (\phi)}\rvert},where \phi is ... 1answer 129 views ### Metric TSP with integer edge cost Given a metric TSP with integer edge cost upper-bounded by a constant C_{\max}, can we find an poly-time algorithm solving this TSP instance? 0answers 30 views ### Complexity of Quadratic Programming where the symmetric matrix Q is positive semidefinite only in the feasible directions playing around with stuff for my dissertation, I derived a quadratic problem in the general form \begin{equation} \begin{aligned} \min_{x} \quad & x^TQx + c^Tx \\ \textrm{s.t.} \quad & Ax \leq ... 1answer 57 views ### How hard is a linear programming with a bounded constraint? Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''. Restate the ... 0answers 336 views ### Zero-knowledge proofs for answers to the P=NP question Are there zero-knowledge proofs for every answer to the P=NP question? For instance, if you have a polynomial-time algorithm of moderate complexity for the graph-coloring problem, then it is easy to ... 1answer 184 views ### What are the odds for a random collection of numbers to have sum less than a certain number? Let's say we have I collections of numbers, N_i numbers in each. A collection may contain repeating numbers. We randomly take one number from each collection. What is the probability for a sum of ... 0answers 48 views ### Logical operations expressed as polynomials Suppose that x,y\in\{0,1\}\subset \mathbb{F}, where \mathbb{F} is a field, which can be assumed of characteristic 0 or arbitrarily large. It is plain that the standard logical operations can be ... 0answers 124 views ### Certificate for computation of ideal class group Is there a known way of producing a certificate that can be used to more quickly verify that an ideal class group of a number field was computed correctly? More formally, I would like to know if there'... 0answers 63 views ### Algorithms to factorize words into product of powers I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references. Let A be a finite set of symbols, are there ... 0answers 57 views ### Subgraph isomorphism problem with linear map I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem: Problem 1: Given two graphs G=(V, E) ... 0answers 18 views ### Reporting uncoverable directed simple cycles in digraphs What is known about cycles in digraphs that can't be member of any of that digraph's vertex disjoint directed cycle covers as illustrated below? in that "cat's eye graph" the green cycle ... 1answer 234 views ### Could somebody suggest a way to determine if a parallelogram contains another parallelogram? I thought of one way to do this. Using the algorithm which determines if a point is inside a parallelogram, one can determine if the polygon contains the point within 2N steps (N=2 for ... 0answers 33 views ### Computational complexity of rate \frac{1}{2} codes We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)... 0answers 90 views ### Promise version of minimum distance It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard. This immediately also says that given a code C, calculating minimum hamming ... 0answers 61 views ### Time complexity of asymmetric sums of divisor function Let \sigma_0:\mathbb{Z}_{\geq 1}\to \mathbb{Z}_{\geq 1} be the divisor counting function. Naively it seems the time complexity of computing \sum_{i=1}^n \sigma_0(i) is at least linear but it can ... 1answer 98 views ### The complexity of expansion ratio (Cheeger constant) of a graph Let G=(V(G), E(G)) be a graph on n vertices and let S be a subset of V(G). The boundary of S, denoted by \partial S, is the set of edges (i, j) such that i \in S and j \in V(G) \... 0answers 62 views ### Counting \bmod 2 number of vertices of sparsely represented polyhedra Given a polyhedronAx\geq b$$is there an NC^1 or an NC^2 algorithm to count the number of vertices \bmod2? Assume A\in\{0,1\}^{m\times n} and b\in\mathbb Z^{m} (m=O(n)) and assume rows ... 0answers 45 views ### Modular counting of integral points under sparse non-negativity Given a polyhedron$$Ax\geq b$$where every entry of A,b are non-negative and A\in\{0,1\}^{m\times n} and there are O(1) (say \leq8) non-negative entries per row of A is it possible to ... 1answer 134 views ### Finding a binary variable assignment to make a matrix with variables singular (over F_p) Consider a square matrix defined over a finite field M\in\mathbb{F}_p^{n\times n} having the following form$$M=\begin{bmatrix}a_{11}+b_{11}x_1&a_{12}+b_{12}x_1&\dots&a_{1n}+b_{1n}x_1\\...
Is the following problem in $PH$ and is it complete for any class? Problem: Is the $i$th bit of the $m$th prime $1$? It appears to require a counting quantifier which has to demonstrate witness is the ...