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
8 votes
2 answers
2k views

Why do almost all points in the unit interval have Kolmogorov complexity 1?

Re-posted from math.stackexchange as I did not get any answers there. I am reading Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, ...
3 votes
1 answer
188 views

How to find the maximum of a sum of squares of sums?

Is there any better than a brute force method for finding the maximum $$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...
  • 33
5 votes
2 answers
173 views

Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

It was shown in P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in a lattice that the construction of a shortest nonzero vector of a Euclidean ...
  • 305
2 votes
1 answer
183 views

Computational complexity and commuting functions, examples and conjectures

History of the question. I was proposing a conjecture here, called Prop. 1. Fedor Pakhomov showed a counter-example. Here I am proposing a slightly weaker version of the conjecture, Prop. 2, that ...
8 votes
1 answer
190 views

Computational complexity and commuting functions

EDIT: in this question, I was proposing a conjecture, Prop. 1. Fedor Pakhomov showed a counter-example. In this new question I propose a slightly weaker conjecture that holds even for that example and ...
13 votes
1 answer
436 views

Can we compute the first $n$ digits of $\pi$ in $F(n)$ time?

I've seen various fast algorithms for computing the first few, or directly the $n$-th, digits of $\pi$. However, it seems to me that all these algorithms assume (see last sentence here) that there are ...
  • 17.6k
1 vote
0 answers
97 views

Frog game on tree graphs is in NP but not in P (NP-complete)?

Problem We can restrict ourselves to tree graphs. What is the complexity of the following problem? Let $G$ be simple connected graph with vertices in $V$, edges in $E$, and a vertex weighted function $...
  • 581
9 votes
1 answer
552 views

Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?

According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable. According to this source, determining whether a ...
  • 11k
1 vote
0 answers
154 views

Future of complexity classes in case NP=P

The P=NP question is still unresolved and there is no hope that the situation will ever change. Assume now the hypothetic situation that P=NP had been confirmed: Questions: what will become of the ...
  • 11.4k
2 votes
0 answers
105 views

On GCD and lattice reduction

$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$. Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector. If $GCD$ is in $NC$ and in ...
  • 13.1k
4 votes
0 answers
74 views

Lattice reduction of basis with non-integer coefficients

Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$. I would like to perform lattice ...
  • 556
1 vote
0 answers
52 views

Finding the optimal arithmetic circuit for evaluating a given polynomial

The Horner's algorithm takes as input a univariate polynomial $f(X)$ and an evaluation point $x$ and computes $f(x)$ using $O(\deg(f))$ field operations. Suppose now that the polynomial $f(X)$ is ...
  • 297
4 votes
0 answers
96 views

Questions in number theory related to $NC$ and $P$-completeness

Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$. Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$. Euclidean algorithm solves both. My question is if either 1 or 2 is in ...
  • 13.1k
1 vote
0 answers
39 views

What is the complexity of elgamal cryptosystem? [closed]

Its clear generation of keys based On cyclic group and its generator for z_p So my question Does finding the generator efect on complexity Moreove does the size of message M effect on the complexity?
  • 11
2 votes
0 answers
77 views

Is orthogonal polygon with crossings count NP-complete?

The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
1 vote
0 answers
97 views

Maximal independent set of size exactly k in interval graphs

I am interested in the following decision problem. Given an interval graph $G$ and a $k\in\mathbb{N}$, is there a maximal independent set (independent dominating set) of size exactly $k$ ? Interval ...
1 vote
0 answers
36 views

If statement in the algebraic group model (AGM)

In the algebraic group model (https://eprint.iacr.org/2017/620.pdf), can one use "if" statement? For example, can one do the following in AGM? input: x, y, z if (x = y) then z = x else z = ...
  • 651
0 votes
1 answer
107 views

Examples of real-time transcendental number and superlinear-time trancsendental number

Computation model is defined as Hartmanis and Stearns 4, it is well known that Liouvilles constant $$C_L=\sum_{i=1}^{\infty} 10^{-i!}$$ is computable in real time or linear time 1, 5 especially ...
1 vote
1 answer
143 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 ...
6 votes
0 answers
51 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 ...
1 vote
1 answer
163 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 ...
2 votes
1 answer
97 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 ...
8 votes
1 answer
268 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 ...
11 votes
1 answer
304 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$. ...
  • 16k
1 vote
0 answers
87 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 ...
0 votes
0 answers
94 views

Small hard instances from integer factorization

looking for "small" instances of NP-complete vertex-disjoint cycle-cover problems it occurred to me that formulating integer factorization as such problems could yield what I am looking for. ...
  • 11.4k
0 votes
0 answers
16 views

Exact algorithms for the 3DCC problem

the $3DCC$ problem asks for the existence of, resp. optimal, vertex-disjoint oriented cycle cover of a digraph without transpositions, i.e. in which every cycle consists of at least three vertices. ...
  • 11.4k
0 votes
0 answers
54 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 ...
  • 1,639
1 vote
1 answer
58 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 ...
  • 135
7 votes
3 answers
250 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 ...
  • 11.4k
0 votes
0 answers
17 views

Complexity of divide&conquer for TSP

It is a known fact that the Held-Karp algorithm that uses Dynamic Programming reduces the complexity of the symmetric TSP with $n$ cities from $O(\frac{(n-1)!}{2})$ for enumerating all tours to $O(2^n\...
  • 11.4k
1 vote
0 answers
31 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 ...
  • 21
3 votes
0 answers
106 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 &...
3 votes
0 answers
37 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 ...
1 vote
1 answer
136 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" ...
1 vote
1 answer
96 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 ...
0 votes
0 answers
77 views

Runtime order of Groebner basis computations over prime field

While there seems to be few resources detailing explicit complexity bounds for computing Groebner Bases over the integers, I'm finding it even harder to search for such bounds for computations over ...
1 vote
0 answers
66 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 ...
0 votes
0 answers
223 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 ...
2 votes
2 answers
161 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) \...
  • 17.7k
10 votes
1 answer
729 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 ...
4 votes
1 answer
104 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?...
  • 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)' = \...
2 votes
0 answers
31 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)...
  • 6,094
0 votes
0 answers
43 views

Find number of overlapping edges in a one-dimensional graph

I have a set of edges $(v_1, v_2), (v_2, v_3),(v_2, v_4)$ where each edge has a weight. Say the weights are 1, 2 and 3 respectively. Then we can visualise it as 3 threads, where the the thread from ...
2 votes
0 answers
91 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 ...
  • 303
2 votes
2 answers
591 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
51 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 ...
  • 757
17 votes
4 answers
5k 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 ...
0 votes
0 answers
60 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 ...
  • 143

1
2 3 4 5
25