All Questions
1,809 questions
19
votes
1
answer
3k
views
Möbius Randomness of the Rudin-Shapiro Sequence
The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows.
Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...
- 24.7k
2
votes
1
answer
848
views
Algorithm for satisfiability of inequalities.
I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...
- 85
18
votes
4
answers
2k
views
Complexity of equitable partitions
We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any ...
- 37.7k
1
vote
1
answer
241
views
Covering max flow arcs by arc disjoint paths
Let $(N,A,s,t,u)$ be a network with node set $N$, arc set $A$, source $s\in N$, sink $t\in N$ and capacity vector $u\in\{1,2,\ldots,T\}^A$, and let $x=(x_a)_{a\in A}$ be a maximum $(s,t)$-flow. Is it ...
- 2,966
3
votes
1
answer
445
views
Diagonalization and classes of computable functions
Fix a standard effective listing $(\phi_e)_{e\in\omega}$ of the partial computable functions from $\omega$ to $\omega$. Let $\mathcal{C}$ be a class of computable total functions $\omega\rightarrow \...
- 21.2k
0
votes
1
answer
456
views
Is the Simplex Method still polynomial when all inequalities are through the origin?
Hello,
I want to solve a linear program using the simplex method, and I know that all my inequalities will pass through the origin (therefore, either my initial solution of (0, ... , 0) is optimal, ...
- 693
3
votes
2
answers
2k
views
Sherali-Adams relaxation
I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...
- 113
5
votes
2
answers
4k
views
sparsity of QR decomposition
Hi, everyone!
I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...
- 51
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
3
votes
1
answer
439
views
Complexity of Labeled Graph Homomorphism
The following recreational math problem has been floating around work:
We're given an $m \times n$ grid ($m,n$ positive integers). We wish to label the elements of the grid with letters so that we ...
- 4,636
2
votes
1
answer
369
views
Maximizing positive definite quadratic using the eigendecompoisition
Consider the problem:
$\textrm{max}\;\; x^T Q x$
subject to $||x||_\infty \leq 1$, where $Q$ is a positive definite matrix.
I believe this problem is NP-hard (although I have only found hardness ...
- 53
3
votes
1
answer
153
views
Counting connected fundamental domains of actions on Cayley graphs
The following question arises, for me, from mathematical music theory:
Write $({\Bbb Z}^n,E_n)$ for the Cayley graph of ${\Bbb Z}^n$
relative to standard free generators.
Given a subgroup $L$ of ${\...
- 17.6k
1
vote
1
answer
1k
views
k-uniform k-partite hypergraph matching in polynomial time
I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers that MO users may provide.
It is well known that for $k\geq 3$ finding ...
- 61
30
votes
5
answers
14k
views
Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
- 303
2
votes
1
answer
137
views
Design constraint systems over the reals
This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
- 30.1k
4
votes
0
answers
218
views
Kolmogorov complexity with bounded ressources
Thanks to symetry of information (i.e $\forall x,y, K(xy) = K(x) + K(y|x) - O(log(|x| + |y|)$), one can easily show that :
$ \exists N \forall x, (|x| = n^{log(n)} and |x| \geq N), \exists y, (|y| \...
user22579
3
votes
2
answers
3k
views
how to model a linear program with step-like cost function in the objective
I have a large linear program with the following details.
d1 to di are the variables, where di is an integer. The constraints are a series of inequalities of the form
d1 < d3 < d7 < d23 (...
- 31
3
votes
1
answer
162
views
Quick tests for Self complementary vertex transitive graphs
Are there any quick tests to determine if a graph is Self complementary vertex transitive? That is if the graph is self complementary vertex transitive the answer should be yes.
- 13.9k
7
votes
1
answer
535
views
Vertex transitive graphs
Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?
- 13.9k
10
votes
2
answers
3k
views
How do you tell if a system of linear inequalities has a solution?
A naive solution would be to optimize a dummy variable via linear programming and see if a result is returned. I imagine there must be a more direct way.
- 693
3
votes
0
answers
3k
views
0,1 solution to system of linear integer equations
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
- 149
5
votes
2
answers
3k
views
symmetric difference of languages - both are in NP and coNP
I have this problem,
Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:
$L_1 \oplus L_2$ = {x | x is in exactly one of $...
- 153
5
votes
0
answers
182
views
Best lower bound for proof complexity of graph asymmetry
Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in $NP$-intermediate. I'm looking for references that study the ...
- 2,993
0
votes
2
answers
148
views
Bounding 2nd Eigenvalue of a Pseudo-Rotation-ish matrix
Let $p,q$ be arbitrary primes.
Let $N = p * q$.
Let $I$ be the $N * N$ identity matrix.
Let $R$ be the $N * N$ matrix defined as follows:
$R[x_0 * p + y_0, x_1 * p + y_1]=1$ if and only if $x_0+1 ...
- 45
3
votes
0
answers
220
views
Could SVD be used to optimize the partial inner-products?
Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...
- 131
6
votes
2
answers
256
views
Form a $\mathbb{Z}^d$ lattice cycle from given lengths
Suppose you are given a list of integer lengths,
e.g.,
$(5,3,2,2,1,1,2,1,1)$.
The task is to decide if they can form a closed cycle
in $\mathbb{Z}^d$ by connecting segments of those
lengths in order, ...
- 151k
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
26
votes
4
answers
7k
views
What would be some major consequences of the inconsistency of ZFC?
Update (21st April, 2019). Removed the reference / initial trigger behind my question (please see comment thread below for the reasons). Am retaining, of course, the actual question, noted both in the ...
- 28.6k
6
votes
1
answer
1k
views
NP-hardness of a graph partition problem?
I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is ...
- 2,993
4
votes
1
answer
830
views
Infinite monkeys computing ... triangle area?
I wonder if it is possible to specialize the question:
(a) What is the probability that a random Turing Machine program
will halt?, to: (b) What is the probability that a random Turing Machine
...
- 151k
11
votes
2
answers
668
views
What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?
Disjoint sets $A$ and $B$ are computably inseparable, if there
is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The
existence of c.e. computably inseparable ...
- 236k
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
4
votes
1
answer
322
views
Is $MIN^P$ search problem (partial order) reducible to $MIN^L$ (linear order) search problem?
Search problem $MIN^P$ is, given a polynomial-time computable predicate that is a partial order, to find its minimum (any will do).
Search problem $MIN^L$ is, given a polynomial-time computable ...
- 356
3
votes
2
answers
584
views
Measure of progress towards a proof
Can one define some measure of progress towards a proof of a statement? I'm not sure if it's even possible for general first order logic statements so let's restrict ourselves to propositional ...
- 31
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
30
votes
4
answers
2k
views
A programming language that can only create algorithms with polynomial runtime?
Has someone constructed a programming language that can construct all the algorithms in P, and no others?
I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...
- 493
3
votes
1
answer
342
views
counting patterns in a word
Do algorithms exist to find all the patterns in a word?
I would like to count all the 3-step increasing sequences (123 i.e. 123, 234 & 345) in some word in the alphabet {1,2,3,4,5}
such as "...
- 22.8k
2
votes
2
answers
2k
views
Solving a system of equations/inequalities that have trigonometric functions on the left-hand side
Is there any known (symbolic) method that solves a system of equations/inequalities that have trigonometric functions on the left-hand side of the system?
Ex) Find $x,y,\theta \in \mathbb{R}$ that ...
- 23
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
7
votes
1
answer
757
views
compression of a Turing machine run sequence
consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...
- 529
1
vote
1
answer
240
views
Conditions for differentiability of minima and minimizers of linear functionals?
Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$.
For every continuous linear functional $F$ on $B$, define
$V(F)=min_{c\epsilon C} F(c)$ and
$S(F)= { \lbrace c \epsilon C :...
- 13
4
votes
1
answer
967
views
Solving for Hamiltonian path with constraints on allowable routes through vertices
Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...
1
vote
0
answers
266
views
Multiobjective semidefinite programming
Let $C$ be size $n \times n^{2}$.
Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.
There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$.
$B$ is ...
- 800
0
votes
1
answer
695
views
Minimum distance between two data sets
Suppose we have two sets of data, $X$ and $Y$, each of which contains
$10$ positive numbers. Now let us order the data sets $X=\left\{ x_{1},\cdots,x_{10}\right\}$,
$x_{1}\ge\cdots\ge x_{10}>0$ and ...
3
votes
1
answer
198
views
bounding the probability that a polynomial is near 0
Given a polynomial $p(x_1,\ldots, x_k)$ in $k$ variables with maximum degree $n$, and $x_1,\ldots, x_k \in [0,1]$. Suppose $\max_{x \in [0,1]^k} p(x) = 1$, can we get an upper bound on the probability ...
- 4,466
6
votes
1
answer
507
views
Complexity of computing expansion of a newform level 18 weight 3 and character [3] - OEIS A116418
I am not familiar with newforms, so this may not make any sense.
OEIS sequence A116418 is Expansion of a newform level 18 weight 3 and character [3]
Numerical evidence suggest that up to $10^5$
$$ \...
- 25.4k
5
votes
1
answer
2k
views
Lovász $\delta$ condition for LLL Algorithm
http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
What is the importance of the $\delta$ parameter for LLL bases called Lovász condition?
...
- 13.9k
1
vote
0
answers
1k
views
How to solve simple bilinear equations under extra linear constraints
Hello,
This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:
$\lambda_i^T u_{...
- 53
1
vote
1
answer
2k
views
Can one efficiently optimize over the inverse of matrix?
Hello,
I have the following problem:
Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...
- 53
3
votes
0
answers
458
views
Connected Sum Decomposition of a Knot
Given a composite knot, is it possible to decompose it in prime knots by an algorithm that runs in polynomial time?
- 405