All Questions
1,809 questions
14
votes
2
answers
2k
views
The flip graph of triangulations
A polygon $P_k$ divided by $k-2$ diagonals into triangles is called a polygonal triangulation. These are the vertices of the triangulation graph $\mathcal P_k$. Two vertices are connected by an edge ...
user6976
14
votes
1
answer
4k
views
Kolmogorov Complexity and Proof Techniques
I'm interested in examples of theorems that employ the proof techniques that are utilized in the proof of the undecidability of Kolmogorov Complexity.
Definition:(Sipser) Let x be a binary string. ...
- 243
14
votes
0
answers
4k
views
Minimum tiling of a rectangle by squares
Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes).
Is there an efficient way to calculate this?
- 1,015
13
votes
6
answers
3k
views
Which model of computation is "the best"?
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
13
votes
3
answers
834
views
Undecidable infinite analogs of NP-complete problems?
In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...
13
votes
4
answers
2k
views
Quantum algorithms for dummies
I want to try my hand at designing quantum algorithms to solve certain problems. I feel like I understand (for example) how Grover's algorithm and Shor's algorithm work, and I'm excited to apply the ...
- 7,633
13
votes
2
answers
4k
views
A language complete for NP intersection co-NP
Hi,
Is there any language $L$ know to be complete for $NP \cap co-NP$, i.e. any language $L^{\prime} \in NP\cap co-NP$ reduces in polynomial-time to $L$ and it is known that $L\in NP\cap co-NP$?
...
- 601
13
votes
2
answers
664
views
Complexity of a weirdo two-dimensional sorting problem
Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
- 19.2k
13
votes
2
answers
1k
views
What is known in general about the liquid transfer problem?
In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
- 2,075
13
votes
1
answer
609
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 ...
- 18.7k
13
votes
2
answers
768
views
How hard (P, NP, NP-hard) is it to compute Schur norms of matrices (as multipliers)?
Given a matrix $A\in M_n(\mathbb{C})$, I will denote by $||A||_\infty$ the operator norm of $A$, as seen acting on the Hilbert space $\mathbb{C}^n$. This makes $M_n(\mathbb{C})$ into a Banach space (...
- 647
13
votes
2
answers
547
views
Can more polynomial time compensate for less polynomial memory?
I'm wondering what is known about the relation between time and memory for polynomial-time algorithms (which are necessarily also polynomial-space). In particular, I would like to learn what is known ...
- 1,616
13
votes
6
answers
3k
views
A decision problem in graph coloring
It'll be great to get a pointer or answer to the following question:
What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily ...
- 261
13
votes
1
answer
1k
views
An efficient isomorphism between finite fields
Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
- 2,576
13
votes
2
answers
555
views
Convergence of the sequence $s_{n+1}=s_n^2-s_{n-1}^2$
$s_{n+1}=s_n^2-s_{n-1}^2$, $s_0=\sqrt{x}$, $s_1=x$
This sequence seems simple, but is pretty confusing. If you try it with integers, you might think that it always diverges to infinity, but if you try ...
- 467
13
votes
1
answer
472
views
Real numbers with given complexity
This may be an easy question or it may be related to a well known open problem in Computer Science.
Let $\alpha>0$. We say that $\alpha$ is computed in time $T(n)$ if there is a Turing machine ...
user6976
13
votes
1
answer
679
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) ...
- 1,311
13
votes
3
answers
834
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
13
votes
1
answer
2k
views
Erdős multiplication problem revisited
This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.
The very problem has been discussed in-depth and, as such, I require no ...
user56218
13
votes
1
answer
598
views
Space Bounded Communication Complexity of Identity
$\bf Definition.$ We define the space bounded communication in the following way. A and B are
supernatural beings capable of computing anything but
they only have a limited amount of memory and that ...
- 18.7k
13
votes
1
answer
712
views
Most computationally efficient Littlewood-Richardson rule
There are many, many different versions of the Littlewood-Richardson rule: the original characterization via Yamanouchi words, Remmel's version, a description via the Poirier-Reutenauer bialgebra, the ...
- 1,989
13
votes
1
answer
973
views
Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?
It is well known that every partial order on a set can be extended
to a linear order on that set. That is, for every partial order
$\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such
that ...
- 236k
13
votes
1
answer
2k
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 ...
user10891
13
votes
1
answer
399
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 \...
- 5,590
13
votes
0
answers
229
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, \...
- 17.7k
13
votes
0
answers
713
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 ...
- 3,897
13
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 ...
- 5,502
12
votes
5
answers
5k
views
Characterize P^NP (a.k.a. Delta_2^p)
What can you say about the complexity class $\text{P}^{\text{NP}}$, i.e. decision problems solvable by a polytime TM with an oracle for SAT? This class is also known as $\Delta_2^p$.
Obviously $\text{...
- 213
12
votes
2
answers
460
views
Testing whether two elements of $\text{SL}(2, \mathbb{F}_{2^n})$ generate the entire group
Given two elements $A,B \in \text{SL}(2, \mathbb{F}_{2^n})$, is there a (computationally inexpensive) test one could perform to check whether together they generate the entire group?
- 223
12
votes
2
answers
3k
views
Is the solution bounded Diophantine problem NP-complete?
Let a problem instance be given as $(\phi(x_1,x_2,\dots, x_J),M)$ where $\phi$ is a diophantine equation, $J\leq 9$, and $M$ is a natural number. The decision problem is whether or not a given ...
- 2,791
12
votes
2
answers
2k
views
What is the probability a random Turing machine is isomorphic to a DFA?
This is a sort of Chaitin/Omega constant type question, and so I do not expect this probability to be computable to arbitrary precision. However, it is also a very practical thing to know from the ...
- 2,392
12
votes
2
answers
2k
views
Connections between Complexity Theory & Set Theory
Inspired by Joshua Grochow and Iddo Tzameret's answers in a post on http://cstheory.stackexchange.com , I would like to get more references on possible connections between complexity theory and set ...
12
votes
2
answers
10k
views
NP not equal to SPACE(n)
Exercise 3.2 of Computational Complexity, a Modern Approach states:
Prove: NP != SPACE(n) [Hint: we don't know if either is a subset of the other.]
I don't know how to solve this problem.
It's in ...
- 663
12
votes
2
answers
4k
views
Can the Legendre symbol be calculated in polynomial time?
Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...
- 7,633
12
votes
1
answer
5k
views
Closest 3D rotation matrix in the Frobenius norm sense
Given a 3 by 3 matrix $M$ I would like to find the rotation matrix $R$ minimizing the Frobenius norm:
\begin{equation}
\|R-M\|_F
\end{equation}
Is there a closed form solution for $R$, or is it ...
- 561
12
votes
2
answers
2k
views
Fold-and-cut problem in three dimensions
The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...
- 851
12
votes
2
answers
3k
views
What impact would P!=NP have on the characterization of BQP?
Many complexity theorists assume that $P\ne NP.$ If this is proved, how would it impact quantum computing and quantum algorithms? Would the proof immediately disallow quantum algorithms from ever ...
- 267
12
votes
4
answers
4k
views
reversible Turing machines
Hello,
Let T be a Turing machine such that
1) it operates on the alphabet {0,1},
2) its set of states is A
3) the language it accepts is $L$ .
Does there exists a Turing machine S which also ...
- 3,897
12
votes
1
answer
685
views
Harvey Friedman's strict reverse mathematics vs. Cook-Nguyen's V$^0$
Harvey Friedman posted several manuscripts [1] proposing a program for "strict" reverse mathematics, in the sense that the base theory should be mathematically natural and coding-free.
In them he ...
- 123
12
votes
2
answers
980
views
Drawing 3-configurations of points and lines with straight lines
It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane....
- 784
12
votes
2
answers
292
views
Permutation search problems with no known $o(n!)$ algorithms
I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
- 333
12
votes
2
answers
589
views
Faster multiplication with a restricted set of multiplicands?
Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product
$$ p=b_1 b_2 \cdots b_n$$
where each $b_i\in A$.
Clearly $n-1$ multiplications suffice to compute $p$; ...
- 3,979
12
votes
2
answers
423
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 ...
- 2,993
12
votes
1
answer
547
views
Seeking references for finding primes infinitely often
I've been pondering this weakened version of the finding primes problem for a while:
Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$?
This differs from ...
- 2,302
12
votes
1
answer
577
views
Are there very strongly pseudorandom permutations?
A pseudorandom permutation can be defined formally as a function $\phi$ from $\{0,1\}^k\times\{0,1\}^n$ to $\{0,1\}^n$ such that for every $x\in\{0,1\}^k$ the function $\phi_x:y\mapsto\phi(x,y)$ is a ...
- 29k
12
votes
1
answer
2k
views
Computing exponential sums rapidly?
I am looking at sums of the form
$\sum_{N\le n \leq N+M} e(P(n))$
where $P\in R[x]$ is a polynomial of bounded degree. Let's say $M\sim c N$ (and $N$ is large).
The question is - when can one ...
- 20.2k
12
votes
0
answers
158
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 ...
- 42.4k
12
votes
0
answers
447
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 ...
- 2,576
12
votes
0
answers
902
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 $...
- 24.7k
11
votes
4
answers
3k
views
Computational complexity of finding the smallest number with n factors
Given $n \in \mathbb{N}$, suppose we seek the smallest number $f(n)$ with
at least $n$ distinct factors,
excluding $1$ and $n$.
For example, for $n=6$, $f(6)=24$,
because $24$ has the $6$ distinct ...
- 151k