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
1 vote
1 answer
166 views

A combinatorial matrix reconstruction problem II

For a positive integer $n$, let an $n$-shuffle be a multiset $S=[(S_i,d_i)|i=1,\ldots,n]$ of pairs $(S_i,d_i)$, where each $S_i$ is a multiset of $n$ numbers containing the number $d_i$. A realization ...
Arnold Neumaier's user avatar
6 votes
0 answers
62 views

Vertex cover in bipartite graphs with bounds on cost and size

Suppose we have a bipartite graph $G$ with non-negative integer vertex costs. We would like to find a vertex cover of cost at most $C$ and size (number of vertices) at most $S$, where $C$ and $S$ are ...
Edith Elkind's user avatar
1 vote
1 answer
201 views

Deciding if given number is a permanent of matrix

The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as $$ \operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)} $$ The sum here extends over all ...
Alexandr Dorofeev's user avatar
3 votes
1 answer
239 views

The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones

What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically ...
user1642683's user avatar
8 votes
1 answer
344 views

Decidable theories with arbitrary complexity

Are there complete finitely axiomatizable first order theories (with equality) with arbitrarily high computational complexity? Here, arbitrarily high (computational) complexity means that for every ...
Dmytro Taranovsky's user avatar
11 votes
1 answer
344 views

Complexity of counting regions in hyperplane arrangements

Let $H_1,\ldots,H_n$ be hyperplanes in $\Bbb R^d$. Denote $\mathcal{H} :=\{H_1,\ldots,H_n\}$ and let $c(\mathcal{H})$ be the number of regions in the complement: $\Bbb R^d\setminus \bigcup H_i$. ...
Igor Pak's user avatar
  • 16.3k
1 vote
0 answers
92 views

Formalizing intuition of search hardness

Basically, this is a search problem of an object that is promised to exist. Suppose we have an object that can be described completely and uniquely by $m$ properties (each n bits). Suppose a search ...
Mohammad Al-Turkistany's user avatar
0 votes
0 answers
86 views

Polynomial-time algorithm for exact projection to polyhedral cone

Given $c \in \mathbb{R}^d$ and $A \in \mathbb{R}^{n \times d}$, project $c$ to the polyhedral cone $\{x \in \mathbb{R}^d \mid A x \leq 0\}$. Is there an algorithm that outputs an exact solution to ...
user76284's user avatar
  • 1,793
1 vote
1 answer
88 views

What resource do Markov and Shi mean when they estimate tensor contraction complexity?

Markov and Shi in their paper Simulating quantum computation by contracting tensor networks define the contraction complexity as follows (page 10): The complexity of π is the maximum degree of a ...
Grwlf's user avatar
  • 135
7 votes
3 answers
291 views

Is there an optimization variant of NP completeness

Question: is there a class of optimization problems for whose solution no efficent algorithm is known, but for which the claimed optimality of a solution can efficiently be verified? Edits: There is ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
40 views

What is the complexity of the matrix multiplication closure for a given generating system?

Given a generating set of $k$ matrices $X = \{M_1, M_2, \ldots, M_k\}$, with $M_i\in \mathrm{Mat}(\mathbb{C},n)$, what is the worst case complexity for computing the algebraic closure w.r.t. matrix ...
ArminJR's user avatar
  • 21
3 votes
0 answers
123 views

Is counting Latin squares #P-complete?

I feel like I should know the answer to this. I did some Googling and didn't easily find the answer... Question: Is counting Latin squares #P-complete? Obviously the corresponding decision problem &...
Rebecca J. Stones's user avatar
3 votes
0 answers
70 views

Is the Kalman Filter computationally optimal for Kalman filtering?

Kalman filtering is known to be a recursive process that minimizes mean square error in linear problems. My question is: has anybody shown that this algorithm is computationally optimal, i.e. that you ...
Diego Méndez's user avatar
1 vote
1 answer
187 views

Reverse engineering a Diophantine equation

Recently, due to the help I had with another question, I was able to find a Diophantine equation of degree in four variables which is the condition to be able to construct a "rational" ...
Thomas Blok's user avatar
1 vote
1 answer
113 views

Problem NP-completeness on a specific graph class

Consider the class of simple connected n/2-regular graphs, n even. Are the maximum clique problem and/or maximum independent set problem NP-complete on such graphs? Is there any known result which ...
Valentin Brimkov's user avatar
1 vote
0 answers
91 views

Fast algorithm to compute nimber product

It is known that nimbers (Grundy numbers) below $2^{2^n}$ form a field with the nim addition $\oplus$ and the nim product $\cdot$. Generally, one can develop an algorithm to compute the product of two ...
Oleksandr  Kulkov's user avatar
0 votes
0 answers
248 views

What is the weakest subsystem of Second-order Arithmetic (or its first-order part) that proves Szemerédi's Regularity Lemma?

The question is in the title. Szemerédi's Regularity Lemma is the following (according to the Wikipedia entry): For every $\epsilon \gt 0$ and positive integer $m$ there exists an integer $M$ such ...
Thomas Benjamin's user avatar
2 votes
2 answers
258 views

Optimizing a multilinear function over the vertices of the cube

Suppose I have $n$ Boolean variables $x_1,\dots,x_n$, and an objective function of the form $f(x_1,\dots,x_n) = \sum_{a_1,\dots,a_n}c_{a_1,\dots,a_n} x_1^{a_1} \cdots x_n^{a_n}$ with $(a_1,\dots,a_n) \...
James Propp's user avatar
  • 19.4k
10 votes
1 answer
846 views

How hard is it to compute the Davenport constant?

The Davenport constant $D(G)$ of a finite abelian group $(G,+)$ is the least positive integer $k$ such that every sequence in $G$ of length $k$ has a zero-sum (nonempty) subsequence. It seems that the ...
The Amplitwist's user avatar
4 votes
1 answer
123 views

Multi-head two-way finite automata versus logarithmic space

It is known that the languages decided by logarithmic-space Turing machines are exactly those decided by finite automata with multiple, bidirectional (2-way) scanning heads. Where could I find a proof?...
Matt's user avatar
  • 41
9 votes
2 answers
1k views

Faster computation of p-adic log

As I see it, $p$-adic integers work very similar to formal power series over $x$ (e g. with regards to Hensel lifting). When it comes to computing $\log P(x)$, one may use the formula $$ (\log P)' = \...
Oleksandr  Kulkov's user avatar
2 votes
0 answers
43 views

Convergent algorithm for minimizing nonconvex smooth function

Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by $$ \ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h)...
dohmatob's user avatar
  • 6,716
2 votes
0 answers
103 views

Computing coefficients of theta functions associated to quadratic forms

If we take an integral positive definite quadratic form $Q$ and set $\Theta_Q(z) = \sum_{k\geq 0}R_Q(k)e^{2\pi ikz}$, what are the most efficient algorithms to compute the $R_Q(k)$? I am aware e.g. of ...
a196884's user avatar
  • 323
2 votes
2 answers
654 views

What is the most "informative" Yes/No math question you know? [closed]

Imagine that alien civilization contacted you and offered to answer one math question. This should be a Yes/No question (so, you cannot ask for a million-digit binary string encoding the answers to a ...
3 votes
0 answers
59 views

Explicit tautologies requiring lots/few uses of modus ponens in minimal proofs

I am interested in minimal length proofs of tautologies in propositional logic. For concreteness, let's fix a particular Frege system $F$ (i.e., sound and complete set of axioms and deduction rules ...
Sprotte's user avatar
  • 1,065
17 votes
4 answers
6k views

Why is fast matrix multiplication impractical?

I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication. I read some content saying fast matrix multiplications are impractical because of large ...
Jiawei Ren's user avatar
0 votes
0 answers
71 views

Shattering of a set of binary classifiers

Let $S$ be a set, and let $\mathcal{F}_{S}=\{f:S\to\{-1,+1\}\}$ be a set of different label assignments. Show that $\mathcal{F}_{S}$ shatters at least $|\mathcal{F}_{S}|$ subsets of $S$. Here is what ...
cbyh's user avatar
  • 143
0 votes
1 answer
270 views

NP-hardness of non-decision problems [closed]

how to show that non-decision problem is NP-hard? So far I could find out that problems which are NP-hard do not have to be decision problems. But how to show a non-decision problem is NP-hard? Is it ...
borekking's user avatar
2 votes
1 answer
168 views

On roots of irreducible quadratics modulo composites

Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$ Is this problem equivalent to any hardness results?
Turbo's user avatar
  • 13.7k
3 votes
1 answer
886 views

Root of polynomials in a finite field

I am looking for a way to find out if a polynomial $P\in \mathbb Z/p\mathbb Z=\mathbb F_p$, of great degree, has roots in $\mathbb F_p$, with $p$ a big prime number. For example : $p=2^{2020}-69$ ...
Dattier's user avatar
  • 3,737
22 votes
2 answers
6k views

$\mathbf{P} = \mathbf{NP}$, what's the problem?

Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$. We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
Dattier's user avatar
  • 3,737
10 votes
0 answers
420 views

Fast method to verify if a point belongs to a given convex $d$-polytope

We are given a $d$-dimensional convex polytope $P\in\mathbb{R}^d$. Assume we have all the supporting hyperplanes describing $P$ and its vertices. Let $S$ be a sequence of $n\gg 1$ points $\mathbb{R}^d$...
Penelope Benenati's user avatar
3 votes
1 answer
179 views

Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation

Given a matrix group $G$ by its generators i.e. $G =\langle A_1,A_2,...,A_k \rangle \leq GL_n(q)$, where each $A_i$'s are matrix in $GL_n(q)$ Q. Does there exist a polynomial time (polynomial in ...
Jins's user avatar
  • 151
0 votes
1 answer
100 views

Turing degrees inside the $\Pi_1^0$ class with top Medvedev degree

I'm sure i have read that the following (or something that implies this) is true Let $X$ be a $\Pi_1^0$ class with top Medvedev degree. Then for every $x\in X$, there is $y\in X$ with $y<_T x$. ...
Niconar's user avatar
  • 75
4 votes
1 answer
341 views

Lower bound on the number of solutions of 2SAT

To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
Alm's user avatar
  • 1,159
5 votes
1 answer
938 views

MIP^*=RE and quantum computation

I recently learned about the MIP^*=RE result. I have to admit that I don't understand big parts of this paper and I am barely familiar with quantum physics. I hope my questions below make sense. I ...
Ioannis Souldatos's user avatar
2 votes
1 answer
140 views

On sets of rectangles that can all together form at least one big rectangle

Let us say a set of $n$ rectangles is rectifiable if all $n$ rectangles together form a big rectangle without gaps or overlaps. Question: How hard computationally is the question of deciding whether a ...
Nandakumar R's user avatar
  • 5,453
2 votes
0 answers
90 views

Blind construction of planar graph with additive spanning tree count

Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
Turbo's user avatar
  • 13.7k
6 votes
1 answer
364 views

Groups in which Computational Diffie Hellman is in $P$ but Discrete Logarithm is not known to be in $P$

The Computational Diffie Hellman (CDH) problem is to compute $g^{XY}$ given $g^X$ and $g^Y$ where $g$ generates the group. The Discrete Logarithm (DLOG) problem is to compute $X$ given $g^X$. The ...
Turbo's user avatar
  • 13.7k
5 votes
0 answers
286 views

Fastest sine of a large power of 2

What is the fastest known way to calculate $\sin(2^{n})$ for large integer $n$? I only need the highest few bits to be correct. I suspect that the compute time required scales with $n$ (and actually ...
bobuhito's user avatar
  • 1,537
3 votes
0 answers
143 views

2-ball billiards in a circle

Consider a 2D circular billiards table with diameter 1m containing two balls with diameter 0.25m. Let each ball start with a speed of 1m/s. In general, this speed could change after the balls hit ...
bobuhito's user avatar
  • 1,537
13 votes
1 answer
640 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) ...
tparker's user avatar
  • 1,243
9 votes
1 answer
538 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 ...
Dmitry Krachun's user avatar
3 votes
2 answers
175 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,.....
antal's user avatar
  • 33
2 votes
1 answer
251 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 ...
H.C Manu's user avatar
  • 733
0 votes
0 answers
79 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 ...
Vahid Shams's user avatar
3 votes
1 answer
393 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}$, ...
Eric_'s user avatar
  • 141
7 votes
0 answers
194 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 ...
Michał Oszmaniec's user avatar
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 ...
user6873235's user avatar
1 vote
0 answers
65 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 ...
Turbo's user avatar
  • 13.7k

1 2
3
4 5
26