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.

Filter by
Sorted by
Tagged with
0
votes
0answers
43 views

Complexity theory on graphs

Let $G$ is a simple graph without loops and multiple edges. Word on graph $G$ is a equivalence class of partial function with finite domain $f:V(G)\to X$, where $X$ is a finite set, and $f\sim g \...
2
votes
1answer
32 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 ...
1
vote
0answers
28 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 ...
0
votes
0answers
55 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 ...
0
votes
0answers
55 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 ...
8
votes
0answers
209 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 ...
0
votes
0answers
67 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 ...
0
votes
0answers
35 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 ...
2
votes
1answer
98 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 $...
0
votes
0answers
121 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}^...
14
votes
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 ...
1
vote
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 ...
4
votes
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 ...
13
votes
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 "...
0
votes
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 $...
1
vote
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 ...
0
votes
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?
0
votes
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 ...
4
votes
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)$ ...
1
vote
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 ...
5
votes
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 ...
2
votes
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 ...
3
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
6
votes
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 ...
3
votes
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 ...
2
votes
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 ...
1
vote
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 ...
1
vote
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 ...
7
votes
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?
2
votes
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 ...
0
votes
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 ...
7
votes
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 ...
0
votes
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 ...
0
votes
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 ...
6
votes
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'...
4
votes
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 ...
1
vote
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)$ ...
1
vote
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 ...
1
vote
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 ...
1
vote
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)...
1
vote
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 ...
0
votes
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 ...
2
votes
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) \...
1
vote
0answers
62 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 ...
3
votes
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 ...
4
votes
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\\...
0
votes
0answers
61 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 ...

1
2 3 4 5
24