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
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 ...
12
votes
1answer
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) ...
3
votes
1answer
97 views

Computing moments of discrete probability distribution

I am wondering whether or not there is a computationally efficient way to compute the first $N$ moments $$m_k=\sum_{n=1}^{N}p_nx_n^k,\;\;\;\;k=1,...,N$$ of a probability mass function with mass $p_1,.....
4
votes
0answers
114 views

Is there a polynomial time algorithm for finding primes?

I was wondering if, given $k$, there is a deterministic polynomial time algorithm (polynomial in $k$) which finds a prime number with $k$ digits. There is clearly a probabilistic one: just take random ...
0
votes
0answers
48 views

Decidability of choosing delay in Takens' theorem

In Dynamical systems theory, Takens' embedding theorem is as follows: Suppose that a measured time series $y(1), y(2), \ldots, y(N)$ lies on a $D$-dimensional attractor of an $n$th-order ...
2
votes
1answer
95 views

Different quantum computation models equivalence

There are different models of quantum computing like quantum circuits, adiabatic or annealing. Another thing to mention is the complexity class BQP. It is pretty much a given that the different models ...
3
votes
1answer
122 views

Fastest way for certain rectangle matrix multiplication

I have $2$ matrices over $\mathbb{N}$, from the size $n \times \sqrt{n}$ and $\sqrt{n} \times n$. I would like to find an efficient way to multiply them. By efficient, I mean better than $n^{2.5}$, ...
17
votes
4answers
2k views

Languages beyond enumerable

A language is a set of finite-length strings from some finite alphabet $\Sigma$. It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings. ...
0
votes
0answers
27 views

Asymptotic probability of a short path in the LEAF problem

When reading about total NP search problems (specifically their oracle versions) I started analysing the computational problem $\text{LEAF}$: An instance $(G,v_0)$ is given by an undirected graph $G$, ...
17
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 ...
5
votes
1answer
1k views

Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called Lovász condition? ...
2
votes
1answer
45 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 ...
34
votes
5answers
3k 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 ...
7
votes
0answers
110 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 ...
1
vote
0answers
43 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 ...
0
votes
2answers
114 views

Optimal path with multiple costs

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and ...
1
vote
1answer
130 views

Complexity of edge coloring graphs with $\Delta(G) \ge n/3$ assuming the overfull conjecture

Closely related to this on cstheory. Let $G$ be graph of order $n$ with $\Delta(G) \ge n/3$. Assume the overfull conjecture. Can we edge color $G$ with minimal number of colors in polynomial time? ...
8
votes
0answers
214 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
votes
1answer
210 views

Games and the right mathematical framework for GANs

Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations. It is an important topic within deep learning. Are ...
0
votes
0answers
58 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 ...
1
vote
0answers
35 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 ...
10
votes
1answer
737 views

What is known in general about the liquid transfer problem?

In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
2
votes
0answers
61 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 ...
15
votes
3answers
4k views

What are the current breakthroughs of Geometric Complexity Theory?

I've read from Wikipedia about Geometric Complexity Theory (GCT) which (if I understood correctly) is a program for coping with the $ P=NP $ problem using algebraic methods. That program seems ...
4
votes
1answer
308 views

Polynomial size embeddings of toric varieties from polytopes?

Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan. $X_P$ is always projective, because the collection of characters corresponding to the points $\...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
101 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
125 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}^...
2
votes
0answers
67 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
139 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
690 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 "...
12
votes
1answer
1k views

Erdős multiplication problem revisited

This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table. The very problem has been discussed in-depth and, as such, I require no ...
0
votes
1answer
126 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 $...
46
votes
7answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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?
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
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)$ ...
5
votes
2answers
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 ...
1
vote
0answers
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 ...
7
votes
3answers
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 ...
2
votes
0answers
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
7
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
381 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
2 3 4 5
24