# 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.

321
questions with no upvoted or accepted answers

**25**

votes

**0**answers

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

**0**answers

923 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 ...

**20**

votes

**0**answers

371 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

**0**answers

462 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 ...

**19**

votes

**0**answers

725 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

**0**answers

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

**0**answers

257 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

**1**answer

554 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

**0**answers

415 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

**0**answers

673 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

**0**answers

657 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 ...

**13**

votes

**0**answers

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

**0**answers

204 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

**0**answers

320 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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

374 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

**0**answers

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

**0**answers

164 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

**0**answers

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

**0**answers

213 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

**0**answers

223 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

**0**answers

153 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

**0**answers

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

**0**answers

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

**0**answers

113 views

### Bi-Hölder embeddings of finite metric spaces

This is a reference request. There is a large body of work, I'm familiar with, that describes the existence of bi-Hölder embeddings of finite metric spaces into Euclidean space (such as this ...

**8**

votes

**0**answers

72 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

**0**answers

201 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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

689 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

**0**answers

416 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

**0**answers

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

**0**answers

301 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

**0**answers

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

**0**answers

246 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

**0**answers

220 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 ...

**7**

votes

**0**answers

211 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

**0**answers

433 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

**0**answers

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

**0**answers

263 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

**0**answers

929 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

**1**answer

176 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

**0**answers

118 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

**0**answers

59 views

### special classes of ideals (eg. toric) that admit faster Buchberger algorithm?

I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold:
What are the precise complexity-...

**6**

votes

**0**answers

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

**0**answers

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

**0**answers

201 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 ...