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.

314 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
25
votes
0answers
1k views

Computational complexity of topological K-theory

I am a novice with K-theory trying to understand what is and what is not possible. Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with ...
20
votes
0answers
921 views

Do we know how to determine the $2^{2020}$ decimal of $\sqrt{2}$?

In the case of $\dfrac{1}{7^{800}}$ it's easy, to find the $2^{2020}$ decimal, but what about the simplest of the irrational numbers. Question: Do we know how to determine the $2^{2020}$ decimal of ...
19
votes
0answers
368 views

Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, ...
19
votes
0answers
461 views

Checking Mertens and the like in less than linear time or less than $\sqrt{x}$ space

Say you want to check that $|\sum_{n\leq x} \mu(n)|\leq \sqrt{x}$ for all $x\leq X$. (I am actually interested in checking that $\sum_{n\leq x} \mu(n)/n|\leq c/\sqrt{x}$, where $c$ is a constant, and ...
18
votes
0answers
722 views

Reference request: Parallel processor theorem of William Thurston

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
15
votes
0answers
335 views

Complexity of a Fibonacci numbers discrete log variation

In my work I encountered the following FIBMOD PROBLEM: Given $k,m$ in binary, decide if there exists $n$ such that $\, F_n = k \,$ (mod $m$). Here $F_n$ is a Fibonacci number. This is a variation ...
15
votes
0answers
254 views

Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where Cells on the tape can hold arbitrary elements of $\mathcal{S}$. The ...
15
votes
1answer
547 views

Are there any natural theories T for which P=NP implies T proves P=NP?

The qualifier "natural" is meant to exclude examples like "PA + P=NP" or "PA + True $\Pi_1$". For concreteness, let's say that "natural" = sound, computably enumerable, with a feasible proof-checker. ...
14
votes
0answers
413 views

Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but: Question: Is there a reformulation of the Dynamic ...
13
votes
0answers
669 views

Why should Algebraic Geometers and Representation Theorists care about Geometric Complexity Theory?

Geometric Complexity Theory has demonstrated that Complexity Theorists should care about Algebraic Geometry and Representation Theory, but, why should Algebraic Geometers and Representation Theorists ...
13
votes
0answers
1k views

Razborov's response to Almost Natural Proofs

This post is about Natural Proofs barrier in computational complexity. There are two recent papers related to this. They are: Amplifying lower bounds by means of self-reducibility by Eric Allender ...
12
votes
0answers
189 views

Does the Angel have to be really smart?

My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy. I'm a big Conway fan, so as you can ...
12
votes
0answers
315 views

Geometric complexity theory for finite fields

Geometric complexity theory (GCT) is an approach via algebraic geometry and representation theory towards the P vs. NP problems and related problems Ketan D. Mulmuley. More precisely, the idea is to ...
12
votes
0answers
864 views

Primes and Parity

This problem is motivated by the polymath4 project. There, the aim was to find an efficient deterministic algorithm for finding a prime larger than $N$. The hope was to find a polynomial algorithm in $...
12
votes
0answers
652 views

Regular languages of matrices and their generating functions

My question is somewhat related to this question. Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
12
votes
0answers
2k views

How can an approach to $P$ vs $NP$ based on descriptive complexity avoid being a natural proof in the sense of Raborov-Rudich?

EDIT: This question has been modified to make it a stand-alone question. Feel free to retract your votes for the previous version. Here are Vinay Deolalikar's paper, and Richard Lipton's first post ...
11
votes
0answers
132 views

Known obstruction for efficient computation of Stable homotopy groups?

Computation of stable homotopy groups (for example of sphere) is hard, but still, not as hard as unstable ones. For unstable homotopy groups there are some results showing that there cannot be ...
11
votes
2answers
365 views

Techniques for proving relaxed one-wayness of functions

Existence of one-way functions is a widely accepted conjecture in complexity theory. A function is one-way if it is computable in polynomial-time but not invertible in polynomial-time (this is ...
11
votes
0answers
1k views

The hardness of computing inverse

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input. Are ...
10
votes
0answers
162 views

Primitive recursive and feasible presentations for nonstandard models of arithmetic

Let us define a countable model $\cal{M}$ = $(M,+_M ,\cdot_M, <_M)$ of $Q$ (Robinson arithmetic) to have a (primitive) recursive presentation if $\cal{M}$ is isomorphic to $(\omega, \oplus, \...
10
votes
0answers
206 views

Collapsing the Linear Time Hierarchy and finite axiomatizability of bounded arithmetic

It is well known that if ${\bf T_2}$ (or $I\Delta_0+\Omega_1$) is finitely axiomatizable, then the Polynomial Hierarchy collapses. Q. Is there any similar relation between $I\Delta_0$ and Linear ...
9
votes
0answers
208 views

Two-player independent set game

Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...
9
votes
0answers
222 views

Is there an efficient algorithm for testing isomorphism of projective planes?

Isomorphism testing is a core problem in computational complexity. Recently, Babai has shown that Graph Isomorphism problem for general graphs can be solved in quasipolynomial time. Long time before ...
9
votes
0answers
150 views

Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?

Like a statement of the kind, ``If the Polynomial Hierarchy (PH) $\neq$ PSPACE then there exists $L \in PSPACE \backslash PH$ which is not PSPACE-complete"? Or is there something else that states ...
9
votes
0answers
2k views

Is Witten's new method of quantization useful for geometric complexity theory?

The Kempf-Ness theorem (see e.g. arXiv:0912.1132) - that the algebraic quotient of geometric invariant theory is also a symplectic quotient - suggests (to me) that certain physical constructions used ...
9
votes
0answers
2k views

Weighted Hamming distance

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, ...
8
votes
0answers
71 views

Is recognizing if a Latin square is isotopic to its transpose more efficient than computing its symmetry group?

Ihrig and Ihrig (2007) described a mathematical method for determining if a Latin square is isotopic to its transpose (where isotopic Latin squares vary by permuting the rows, columns and symbols). ...
8
votes
0answers
199 views

Is Hankelability NP-hard?

This question was previously asked on cstheory but with no answers or substantive comments. I am trying to write code to detect if a matrix is a permutation of a Hankel matrix. Here is the spec. ...
8
votes
0answers
189 views

Ricocheting pinball-like shot: Complexity?

Suppose one has $n$ perfect two-sided mirror segments in the plane $\mathbb{R}^2$. The segments are open, excluding their endpoints. They are disjoint as closed segments, i.e., no pair shares an ...
8
votes
0answers
232 views

Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...
8
votes
0answers
136 views

Can the isomorphism relation for countable models become harder when adding finitely many constants?

I am particularly interesting in the case where $T$ is o-minimal, but I would be interested in any theory $T$ (or even an $L_{\omega_1,\omega}$-sentence) which has this property. Context: view the ...
8
votes
0answers
677 views

Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3? I know it is NP-complete for the ...
7
votes
0answers
388 views

Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere

Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
7
votes
0answers
112 views

Does the problem of recognizing 3DORG-graphs have polynomial complexity?

A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...
7
votes
0answers
296 views

Surprising mathematical consequences of of $\mathbf{P} = \mathbf{NP}$

I got interested in the mathematical consequences of $P = NP $ after reading this post, Any important consequences with presupposition of P≠NP . Wang conjectured that if a finite set of Wang tiles ...
7
votes
0answers
1k views

Why is solving polynomial systems NP hard?

Solving polynomial systems is known to be a NP hard problem; however it is not completely clear to me where this complexity comes from. My interest is in the case of systems of multivariate ...
7
votes
0answers
245 views

Can primes be (almost) random sequence in von Mises sense?

Random models for primes (such as Cramer's model) have been extensively used for informal justification of various conjectures involving primes. It is crucial to understand in what sense sequence of ...
7
votes
0answers
209 views

Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?

Landau's function $g(n)$ is the largest order of an element of the symmetric group $S_n$. Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$. In general $g(n)$ is ...
7
votes
0answers
432 views

Is simultaneous diophantine approximation (in a weaker sense) NP hard?

The traditional problem of simultaneous diophantine approximation is: Given a set of rational numbers $g_1,\ldots,g_d$, an integer $N$, and a rational $\gamma>0$, is there an integer $W$ with $1\...
7
votes
0answers
233 views

When is a reduction not a reduction?

Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of "...
7
votes
0answers
260 views

Feasible Type Theories

I am looking for references about efficient type theories, efficiency in the sense of computational complexity, and type theory in the sense of Martin-Lof's type theories. Has there been any studies ...
7
votes
0answers
925 views

Computational complexity of multiplication in a nilpotent group?

What is the computational complexity of multiplication in a Carnot group ? Background: A Carnot group is a real nilpotent Lie group $N$ whose Lie algebra $Lie(N)$ admits a direct sum decomposition ...
7
votes
1answer
174 views

Complexity of integer programming with added predicates

A classical theorem in Integer Programming by Lenstra says that any integer system $$A x \le b$$ can be solved in polynomial time, where $A \in \mathbb{Z}^{m \times n}, x \in \mathbb{Z}^n, b \in \...
6
votes
0answers
112 views

The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory

Almost 30 years ago, a number of folks in provability logic tried to show that GL (see for instance the excellent survey by Rineke Verbrugge here) is indeed the logic of $I\Delta_0+\Omega_1$ (in the ...
6
votes
0answers
80 views

Finding the maximal component of a vector in sublinear time

Given a vector $u \in \Bbb R^n$, finding the value of the largest component of $u$ needs linear time in $n$. However, what if we additionally know that $u$ lies in some linear subspace $U \subset \Bbb ...
6
votes
0answers
106 views

On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate $P=BPP$ in $1986$. They do this without getting into circuit lower bounds and from a different view ...
6
votes
0answers
200 views

Complexity of scissors congruence?

Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...
6
votes
0answers
87 views

Combinatorial region-halfplane incidence structures

I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate. Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...
6
votes
0answers
214 views

Multidimensional hook length formula

A well-known hook length formula states that the number of ways to arrange the elements of $[n]$ in a Young tableau with $n$ cells so that all columns and rows are increasing is $\frac{n!}{\prod_c h(c)...
6
votes
0answers
219 views

Complexity of approximating the size of the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$ It is NP-hard to compute $S_M$ exactly I believe by applying the ...

1
2 3 4 5
7