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,300
questions
7
votes
0
answers
199
views
Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs
Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a ...
- 965
34
votes
5
answers
4k
views
What are the strongest arguments for a genuine quantum computing advantage?
Despite having become a fairly mature field with enormous sums of money dumped into research and development, there does not as yet exist a formal proof that quantum computation actually provides an ...
- 756
1
vote
0
answers
66
views
On perfect matchings on planar graphs - is there a linear time deterministic algorithm?
The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.
MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
- 13.7k
2
votes
1
answer
216
views
Fast inverse of asymmetric diagonally dominant matrix with diagonal 1 and non-positive off-diagonals
I am interested in ways to obtain (even approximately) the inverse of an asymmetric diagonally dominant matrix with diagonal 1 and non-positive off-diagonals.
Formally, let $A$ be a $n\times n$ matrix ...
- 59
1
vote
0
answers
158
views
Does fraction-free Gaussian elimination use fractional row operations?
I would like to understand whether Gaussian elimination of an integer matrix, which uses only row operations of the form
Addition (or subtraction) of row $i$ to row $j$
can be performed in ...
- 111
0
votes
0
answers
103
views
Exact Gaussian elimination of a rational matrix
If a matrix $A$ consists of rational elements, and we have access to only row operations of the form
Row addition/subtraction from row $i$ to row $j$
Row exchanging row $i$ with row $j$
What is the ...
- 111
2
votes
0
answers
66
views
A sub-logarithmic complexity in Analysis and N.Th
The question will be about complexity $\ \mathcal C(p)\ $ being positive and the same for all primes $\ p.$
Function $\ \mathcal Q\ $ is defined in the set of finite sequences of positive rational ...
- 4,686
8
votes
0
answers
236
views
Size of 3-SAT assignments
Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is ...
- 3,809
0
votes
0
answers
79
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 ...
user409739
2
votes
1
answer
116
views
Family of PTIME sets where it is hard to name elements
Call a function$$\mathbb{N}\times \mathbb{N}\to \{0, 1\}, \quad (n, m)\to f(n, m)$$computable in polynomial time in $\log n+\log m$ a PTIME family.
Given a PTIME family $f$ call a computable function $...
user409739
0
votes
0
answers
134
views
On a deterministic primes search problem
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}^...
- 13.7k
18
votes
4
answers
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 ...
- 197
2
votes
0
answers
71
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 ...
- 21
4
votes
0
answers
167
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 ...
- 5,563
13
votes
3
answers
808
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 "...
0
votes
1
answer
136
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 $...
- 1
1
vote
1
answer
146
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 ...
- 21
0
votes
1
answer
133
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?
- 59
4
votes
1
answer
141
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)$ ...
- 1,758
1
vote
0
answers
80
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 ...
- 690
6
votes
2
answers
2k
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 ...
- 552
2
votes
0
answers
146
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 ...
- 147
3
votes
1
answer
161
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 ...
- 13.7k
1
vote
1
answer
146
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 ...
- 107
1
vote
0
answers
176
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 ...
- 24.2k
0
votes
0
answers
100
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 ...
- 328
7
votes
1
answer
743
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 ...
- 13.7k
3
votes
1
answer
4k
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 ...
- 51
2
votes
0
answers
59
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 ...
- 21
1
vote
0
answers
532
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 ...
- 59
1
vote
1
answer
215
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 ...
- 107
7
votes
1
answer
169
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?
- 436
2
votes
0
answers
132
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 ...
- 21
0
votes
1
answer
119
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 ...
7
votes
0
answers
464
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 ...
- 12.7k
0
votes
1
answer
221
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 ...
- 131
6
votes
0
answers
159
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'...
- 1,806
5
votes
1
answer
119
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 ...
- 477
1
vote
0
answers
66
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)$ ...
- 101
1
vote
0
answers
25
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 ...
- 12.7k
1
vote
1
answer
246
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 ...
- 19
1
vote
0
answers
45
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)...
- 71
1
vote
0
answers
101
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 ...
- 71
2
votes
1
answer
182
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) \...
- 620
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\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 ...
- 13.7k
3
votes
0
answers
50
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 ...
- 13.7k
4
votes
1
answer
202
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\\...
- 153
0
votes
0
answers
62
views
On complexity of a particular prime problem
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 ...
- 13.7k
2
votes
0
answers
86
views
Computing bipartite matching of size $k$?
Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$?
The problem of computing all perfect matchings is #P-complete. But I ...
- 241
1
vote
0
answers
209
views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
- 13.7k