All Questions
1,809 questions
17
votes
8
answers
2k
views
Examples of ubiquitous objects that are hard to find?
I've been wrestling with a certain research problem for a few years now, and I wonder if it's an instance of a more general problem with other important instances. I'll first describe a general ...
17
votes
3
answers
6k
views
The cone of positive semidefinite matrices is self-dual? (reference needed)
I'm seeking a reference for the following fact.
The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar).
This result is relatively easy to prove, has been known for a long time,...
- 1,513
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
17
votes
1
answer
2k
views
Forcing over set theory versus forcing over arithmetic
I've been trying to understand better some of the research on forcing over bounded arithmetic and its connections with lower bounds in complexity theory. For example, Takeuti and Yasumoto have some ...
- 82.7k
17
votes
2
answers
4k
views
Optimizing the condition number
Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns $...
- 96.4k
17
votes
1
answer
874
views
An NP-hard $n$ fold integral
We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\...
- 627
17
votes
1
answer
870
views
How fast can we numerically calculate Kloosterman sums?
Define the usual Kloosterman sum by $$S(m,n;c) = \sum_{\substack{x \pmod{c} \\ (x,c) = 1}} e\Big(\frac{mx + n\overline{x}}{c}\Big),$$
where $x \overline{x} \equiv 1 \pmod{c}$, and $e(x) = e^{2 \pi i x}...
- 4,671
17
votes
1
answer
960
views
Polynomial-time algorithm to compare numbers in Conway chained arrow notation
I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
- 171
17
votes
0
answers
449
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 ...
- 992
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
16
votes
2
answers
5k
views
How to compute all irreducible representations of a finite group ? (how GAP is doing this?)
Let us "take" a finite group G. Here "take" I mean any type of group-theoretic description you prefer: e.g. as an explicit subset of GL (or other group) or Cayley table, whatever.
Question: How ...
- 24.9k
16
votes
3
answers
2k
views
Are there any known quantum algorithms that clearly fall outside a few narrow classes?
I'm trying to refresh myself on quantum algorithms and have been skimming Childs and van Dam's 2008 RMP paper among other things. From my preliminary surfing it looks like the known quantum algorithms ...
- 15.4k
16
votes
5
answers
4k
views
What are the most important results (and papers) in complexity theory that every one should know?
A few years ago Lance Fortnow listed his favorite theorems in complexity theory:
(1965-1974)
(1975-1984)
(1985-1994)
(1995-2004)
But he restricted himself (check the third one) and his last post is ...
16
votes
4
answers
1k
views
Representing mathematical statements as SAT instances
The following problem (call it THEOREMS) belongs to class NP.
Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary.
Output: "Yes" if ...
- 781
16
votes
3
answers
1k
views
symmetric integer matrices
Suppose I have a symmetric positive definite matrix $M$ with integer entries. I want to decide whether $M = A A^t,$ with $A$ likewise integral. I assume that decision problem is NP-complete, as is the ...
- 96.4k
16
votes
5
answers
2k
views
Characterizing visual proofs
``Proofs without words'' is a popular column in the Mathematics magazine.
Question: What would be a nice way to characterize which assertions have such visual proofs? What definitions would one need?...
- 313
16
votes
2
answers
714
views
Is this kind of "Gerrymandering" NP-complete?
[I posted this on Math Stack Exchange about two weeks ago, but didn't get any reply, so I'm trying it here.]
Consider the following simplified form of "Gerrymandering": You have $n^2$ ...
- 263
16
votes
3
answers
918
views
What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$
Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...
- 311
16
votes
3
answers
2k
views
Algorithmic complexity of formal proof verification?
In this question, suppose $S$ is some popular real-world automated proof system that is stronger than or equivalent to Peano Arithmetic. I would be happy with a positive answer to the following for ...
- 11.2k
16
votes
2
answers
2k
views
Structure theorems for Turing-decidable languages?
Languages decidable by weak models of computation often have certain necessary characteristics, e.g. the pumping lemma for regular languages or the pumping lemma for context-free languages. Such ...
- 23k
16
votes
4
answers
3k
views
Zero-knowledge proof of positivity
If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?
My bounty is ending ...
16
votes
2
answers
603
views
NP-hardness of finding 0-1 vector to maximize rows of {-1, +1} matrix
Consider the following discrete optimization problem: given a collection of $m$-dimensional vectors $\{ v_1, \dots, v_n \}$ with entries in $\{-1, +1\}$, find an $m$-dimensional vector $x$ with ...
- 163
16
votes
1
answer
3k
views
Evidence that Graph Isomorphism problem is not $NP$-complete
Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...
- 2,993
15
votes
3
answers
10k
views
Can you efficiently solve a system of quadratic multivariate polynomials?
Given a system of 2nd-degree polynomials, $P=\{p_1,\dots,p_m\}$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find a common zero of all of these polynomials? In other words, ...
- 253
15
votes
4
answers
1k
views
Determining if some permutation of a vector satisfies a system of linear equations
Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?
- 623
15
votes
3
answers
4k
views
Complexity of computing matrix rank over integers
Does computing the rank of an integer matrix have complexity polynomial in the size of the input?
The Gaussian elimination algorithm is polynomial in the number of elementary operations (addition and ...
- 481
15
votes
2
answers
2k
views
What's known about the relationship about EQP and BQP?
EQP is the class of problems solvable deterministically using a quantum computer in polynomial time - that seems to me to be a good analogue to P, whereas BQP is the quantum analogue of BPP.
It ...
- 2,019
15
votes
1
answer
1k
views
Is deciding if one planar graph is dual to another really NP-hard (Wikipedia claim)?
Wikipedia claims (permanent link) without reference:
Testing whether one planar graph is dual to another is NP-complete.
Another claim with reference:
For any plane graph G, the medial graph of ...
- 25.4k
15
votes
7
answers
3k
views
Compressing Graphs (Kolmogorov complexity of graphs)
What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...
user3409
15
votes
2
answers
2k
views
How did the Baker-Gill-Solovay paper come to be?
How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...
user44143
15
votes
1
answer
1k
views
(Very) Large numbers, Chaitin's incompletness theorem and a specific upper bound
Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>...
- 9,330
15
votes
1
answer
1k
views
Is there a known primitive recursive upper bound on the nth "Zhang prime"
(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...
- 6,287
15
votes
2
answers
3k
views
How to compute the rank of a matrix?
Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D.
Here's the actual ...
- 12.6k
15
votes
1
answer
742
views
Computing van Kampen diagrams
If G is a finitely presented group (with generating set X) and w is a word over X such that
w=1 in G, then the latter can be witnessed by a so called van Kampen diagram for w, which is
a planar ...
- 151
15
votes
3
answers
1k
views
Is this strange problem NP-complete?
The following quadratic expression can be simplified:
(x+1)(x+2) + (x+1)(x-3) + 2x(2x-1) - (3x+1)(x-3) - 2x(x+2).
What is the easiest way of doing the simplification? (It would be good to think ...
- 29k
15
votes
2
answers
512
views
Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?
Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by $\pi.(\sigma_1,\...
- 4,902
15
votes
0
answers
487
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 ...
- 6,652
15
votes
0
answers
424
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 ...
- 21.1k
15
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 ...
- 5,502
15
votes
1
answer
794
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.
...
- 333
14
votes
3
answers
2k
views
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
14
votes
3
answers
3k
views
Will quantum computing kill cryptography ? [closed]
I apologize as this question is not really mathematical, and therefore perhaps not
well-suited for this site. Please feel free to close it if you think it is not. My reason
for asking it here is that ...
- 26k
14
votes
7
answers
3k
views
Most 'obvious' open problems in complexity theory
What open problems in computational complexity theory have the most 'obvious' answers, regardless of whether that answer is true or false? The problems I'm talking about certainly have more 'obvious' ...
14
votes
5
answers
1k
views
Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from $1$
Found this on Complexity Zoo warning expired certificate
check NP Over The Complex Numbers.
[BCS+97] show the following striking result. For a positive integer $n$, let $t(n)$ denote the minimum ...
- 25.4k
14
votes
3
answers
3k
views
Definition of relativization of complexity class
Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$?
Usually, these classes and their relativizations seem to be defined in an ad-hoc ...
- 3,475
14
votes
2
answers
4k
views
Best-case Running-time to solve an NP-Complete problem
What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...
- 597
14
votes
6
answers
4k
views
Non-constructive proofs vs. efficient algorithms
My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof begins, "a constructive ...
- 24.2k
14
votes
2
answers
750
views
Correct to characterise NP set as P-time image of P set?
[I'm not familiar with the terminology, so when I write P (resp. NP) set, I mean a subset of the integers whose membership function is a decision problem in P (resp. NP).]
Is it correct to say that a ...
- 2,885
14
votes
3
answers
410
views
Exact coverability of $\mathbb{Z}_n$ by cyclic shifts of a given set -- easy? NP-complete?
Recently Ernest Davis asked me about the following computational problem: we're given as input a composite integer $n$, a divisor $k$ of $n$, and a subset $S \subset \mathbb{Z}_n$ of size k. The ...
- 9,823
14
votes
1
answer
3k
views
Can Shor's Algorithm be modified to run efficiently on a classical computer?
Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...
- 2,649