All Questions
1,809 questions
8
votes
3
answers
2k
views
Transforming a binary matrix into triangular form using permutation matrices
I am interested in the complexity of the following problem:
Given an $m\times n$ binary matrix $M$, can we permute its rows/columns to obtain a triangular matrix?
I am also interested in ...
- 1,271
8
votes
1
answer
533
views
Fastest algorithm for counting perfect matchings in a general graph
Let $G(V,E)$ be a undirected graph. I am interested in the fastest known algorithm for counting the number of perfect matchings in $G(V,E)$ (which is known to be in $\#P$). In particular, what is the ...
- 155
8
votes
3
answers
1k
views
P vs. NP resistant problems
According to Stephen Cook on wikipedia, http://en.wikipedia.org/wiki/P_versus_NP_problem
...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a ...
- 26.9k
8
votes
1
answer
220
views
Is there a good computer program for searching for endomorphisms between finite algebras which make diagrams commute? Is this problem NP-complete?
Let $(X,*),(Y,*),(Z,*)$ be finite algebras. The binary operations $*$ are not required to satisfy any identities though I am interested in the special case where $*$ is associative. Suppose that $f:X\...
8
votes
1
answer
448
views
Is there any real quadratic ring for which the Euclidean algorithm is polynomial?
We know from Rolletschek's work that the Euclidean algorithm of $\mathbb{Z}[i]$ is polynomial. Indeed, let $n$ be the maximum number of steps in the Euclidean algorithm applied to $u,v \in\mathbb{Z}[i]...
- 433
8
votes
1
answer
653
views
Interesting complexity classes $PR \subsetneq c \subsetneq R$
I'm working on a proof-checker that can verify termination proofs. The fundamental method it provides for constructing such proofs is to translate the program into primitive recursion. Basically, I ...
- 223
8
votes
1
answer
790
views
Are problems in complexity theory dependent on set theory?
I was pondering the fact that maybe the classical hard complexity-theoretic questions are undecidable, not because they are so themselves, but because some set-theoretic foundations makes the ...
- 123
8
votes
1
answer
3k
views
Polynomial-time quantum algorithms for lattice problems (GapSVP, SIVP, LWE)
The author of a recent preprint claims to have found polynomial-time quantum algorithms for solving the following lattice problems: the Decisional Shortest Vector Problem (GapSVP), the Shortest ...
- 157
8
votes
1
answer
225
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 ...
- 469
8
votes
1
answer
475
views
How do you compute the primes of bad reduction?
Suppose that I am given a subscheme $Y$ of $\mathbf{P}^n_{\mathbf{Z}}$, flat over $\operatorname{Spec}\mathbf{Z}$ and with smooth generic fiber $Y_{\mathbf{Q}}$, defined by the vanishing of some ...
- 4,746
8
votes
3
answers
472
views
Can we efficiently compute a third Nash Equilibrium, given two?
A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ payoff matrix $A$. If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's ...
- 693
8
votes
2
answers
485
views
Efficient computation of the least fraction with square denominator greater than the square root of 2.
The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a ...
- 6,199
8
votes
1
answer
335
views
Existence of Randomized polynomial time algorithm and some arithmetic analog of $ACC^0$ circuits for Factoring of primitive polynomials before LLL?
Before LLL came along in $1982$ there was no deterministic polynomial (in degree and number of bits in coefficients) way to factor square free primitive polynomials in $\Bbb Z[x]$.
However was there ...
user94040
8
votes
2
answers
3k
views
How to determine if there exists a non-zero vector in the kernel
If you are given a $0$-$1$ circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel?
Could this problem ...
- 3,377
8
votes
1
answer
345
views
An explicit IP algorithm for chess?
If I have 2 large graphs to be tested for isomorphism, and can communicate with some (powerfull but untrusted) machine, I can choose graph at random, permute vertices, ask machine to guess which one ...
- 743
8
votes
1
answer
716
views
Finding colinear points in F_q^n
Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit.
Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let $A,...
- 47.4k
8
votes
2
answers
596
views
Question about polynomials over finite fields
This is a special case of this question.
Let $\mathbb{F}$ be a finite field and $\mathbb{F}_{\leq d}[x,y]$ the set of bivariate polynomials over $\mathbb{F}$ of degree at most $d\ll|\mathbb{F}|$. Do ...
- 125
8
votes
2
answers
355
views
Isomorphism problem on the class of induced subgraphs of a hypercube
A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...
- 3,463
8
votes
3
answers
947
views
Boolean Cube of Primes
For a large enough $n$, and a parameter $ m $ I'm looking for a subset of the prime numbers in the range $[n,2n]$ with a unique structure. I am looking for a prime $p$ and a set of $m$ positive (not ...
- 273
8
votes
2
answers
246
views
Are sums of 0-1 Pareto efficient vectors Pareto efficient?
Does there exist $m,n\ge1$, an $m \times n$ matrix $A$, and a vector $x \in \mathbb{R}^n$ such that:
The entries of $A$ are $\in \{0, 1\}$.
For all pairs of columns $u, v$ of $A$ the entries of $u - ...
- 388
8
votes
0
answers
164
views
Is there a substructure-preservation result for FOL in finite model theory?
It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
- 21.1k
8
votes
0
answers
360
views
Worst-case complexity of calculating homotopy groups of spheres
Is the best known worst-case running time for calculating the homotopy groups of spheres $\pi_n(S^k)$ bounded by a finite tower of exponentials? How high is a tower? Does $O(2^{2^{2^{2^{n+k}}}})$ ...
- 827
8
votes
0
answers
237
views
Size of 3-SAT assignments
Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is ...
- 3,979
8
votes
0
answers
462
views
Inverse polynomial map $\mathbb{Z}^2\to\mathbb{Z}^2$ growing faster than $2^{2^n}$
Let $P, Q\in \mathbb{Z}[x, y]$ be polynomials with zero constant terms. Assume the induced map $\phi_{P, Q}:\mathbb{Z}^2\to\mathbb{Z}^2$ is injective. An example is $P=x+x^3 y^2, Q=y+x^2 y^3$.
Can the ...
- 219
8
votes
2
answers
1k
views
Minesweeper as a linear algebra problem
I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
- 361
8
votes
0
answers
88
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). ...
- 1,327
8
votes
0
answers
231
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 \...
- 343
8
votes
0
answers
226
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.
...
- 3,377
8
votes
0
answers
200
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 ...
- 151k
8
votes
0
answers
225
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 ...
- 25.4k
8
votes
0
answers
288
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 ...
- 2,993
8
votes
0
answers
143
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 ...
- 1,979
8
votes
0
answers
1k
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
...
- 785
8
votes
0
answers
1k
views
Infinite Linear Programming
I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
- 133
8
votes
0
answers
753
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 ...
- 161
7
votes
3
answers
2k
views
Decidable but nonrecursive sets
Until recently, I believed that recursive=decidable,
subscribing to this Wikipedia quote:
"In computability theory, a set is decidable, computable, or recursive if there
is an algorithm that ...
- 151k
7
votes
2
answers
2k
views
Number theory and NP-complete
What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.
- 800
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an ...
- 6,962
7
votes
2
answers
2k
views
Strassen's algorithm
I am reading Landsberg's "Tensors: Geometry and Applications". Here he mentions tensor formulation of Strassen's algorithm and shows that the rank of Strassen's matrix multiplication tensor is $7$ and ...
- 13.9k
7
votes
2
answers
909
views
Formula for volume of a convex polytope
So I've been searching around the internet for some answers to this, but I currently have a set of linear constraints: $Ax = b, Cx \le d$ for matrices $A \in \mathbb{R}^{n \times m}$, $b\in \mathbb{R}^...
- 81
7
votes
4
answers
884
views
Is the classification of finite p-groups a smooth problem?
Fix a prime $p$. Then the question is about the difficulty of classifying finite $p$-groups. Originally I was going to ask if this was a "wild" problem but thanks to Joel David Hamkins' answer to ...
- 9,132
7
votes
2
answers
7k
views
Computational complexity of calculating the nth root of a real number
Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example:
Jean-Michel Muller, "Elementary Functions: ...
- 385
7
votes
2
answers
1k
views
Complexity of Turing Machine behavior
If one looks at the code for a Turing Machine (TM) with
$q$ states and, let's say, $2$ symbols, they all look
pretty much the same:
A list of $5$-tuples:
$$
< state, symbol{-}read, symbol{-}to{-}...
- 151k
7
votes
1
answer
484
views
Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs
I believe correctness about clique in even-hole-free graphs
of graphclasses.org
and the paper Vertex elimination orderings for hereditary graph classes, Pierre Aboulker, Pierre Charbit, Nicolas ...
- 25.4k
7
votes
2
answers
1k
views
Is a given point in the interior of the convex hull of a given finite collection of points?
Suppose I have the convex hull $P$ of a finite collection of points in $\mathbb{R}^d,$ and I want to see whether a point $p$ is contained in $P.$ This is a standard (some would say the standard linear ...
- 96.4k
7
votes
2
answers
2k
views
Why is "P = NP implies EXP has circuit of $2^n/n^" interesting? [Soft, Philosophical]
For example, "P=NP implies PH=P" is interesting ... because most of us don't believe PH=P, so it provides strong evidence P != NP.
On other hand, "P=NP implies EXP has circuit of $2^n/n$ size" seems ...
7
votes
2
answers
763
views
Computational complexity of the word problem for semi-Thue systems with certain restrictions
The word problem (from wikipedia).
Given a semi-Thue system T: = (Σ,R)
and two words , can u be transformed
into v by applying rules from R?
This problem is undecidable, but with a certain ...
- 613
7
votes
2
answers
2k
views
Computational complexity of unconstrained convex optimisation
What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
- 561
7
votes
1
answer
360
views
Does the Hirsch conjecture hold for $n < 2d$?
The Hirsch conjecture asserts that the graph (i.e. $1$-skeleton) of a $d$-dimensional convex polytope with $n$ facets has diameter at most $n - d$.
After being open for decades, Francisco Santos has ...
- 7,857
7
votes
2
answers
561
views
Linear equations with absolute values
Assume we have a set of equations in $x \in \mathbb{R}^n$
$$|a_i\cdot x|=b_i$$
where $a_i \in \mathbb{R}^n$ and $b_i>0$ are given.
Could such a system be solved efficiently?
In a theoretical ...
- 165