All Questions
1,809 questions
1
vote
0
answers
74
views
TSP: Approximation Ratio of the Double Tree Heuristic after Diagonals have been Removed
In their article "Double-Tree Approximations for the Metric TSP: Is the Best One Good Enough?", Vladimir Deineko and Alexander Tiskin derive a lower bound for the approximation ratio of the double-...
- 13.2k
7
votes
1
answer
288
views
What is the Essential Reason that allows a PTAS for the EUCLIDEAN TSP?
Questions:
Is there some understanding of the reason, why the euclidean TSP allows a PTAS, whereas the metric TSP in general does not and, is the PTAS stable under sufficiently small perturbation of ...
- 13.2k
1
vote
1
answer
203
views
infinitary logic and partial fixed point logic
Is there a property definable in finite-variable infinitary logic $L^{\omega}_{\omega\infty}$ but not definable in partial fixed point logic FO(PFP) ?
- 41
10
votes
1
answer
595
views
Fast checking that overdetermined polynomial system does not have a solution
As a result of some inductive procedure for each $n$ I have a system of about $n^2$ polynomial equations with $n$ variables with integer coefficients, which can be precisely computed. As the system is ...
- 728
4
votes
1
answer
750
views
submatrix of a given size with maximum frobenius norm
Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
- 859
4
votes
1
answer
225
views
Approximate the square root of (1-X) efficiently through (nested) products
Currently, I encountered a problem of approximating the following
series:
$$
(I-X)^{-\frac{1}{2}}=I+\frac{1}{2}X+\frac{1\cdot3}{2\cdot4}X^{2}+\frac{1\cdot3\cdot5}{2\cdot4\cdot6}X^{3}+\ldots
$$
where ...
- 133
3
votes
1
answer
509
views
Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality
The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
- 867
3
votes
2
answers
297
views
Conjecture of a subset of Wang tile which might be decidable
From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature:
The left color and ...
- 867
2
votes
0
answers
120
views
integrality of a linear program -- binary equality constaints
Consider the following linear program:
$\left\{
\begin{array}{l}
\underset{x}{max} \;\;c^Tx\\
[I, \;B]x = \mathbf{1}\\
x\geq 0
\end{array}
\right.$
where $c$ is a vector ...
- 127
6
votes
1
answer
949
views
Complexity of counting words of given length in regular or context-free language
Let $L$ be a regular or context-free language over
alphabet $\{0,1\}$.
What is the complexity of counting words of length $n$ in $L$?
Is it possible to efficiently find if for given $n$
all words ...
- 25.4k
8
votes
4
answers
2k
views
NP-hard problems in linear algebra and real analysis [closed]
I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent.
I would thus like to collect in this thread a list of ...
4
votes
1
answer
3k
views
optimization of inverse matrix with constraint on matrix elements
everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...
- 49
2
votes
1
answer
977
views
Is undirected short-simple-path-through-3-vertices decidable in polynomial time?
Consider the following language:
$L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$.
($G$ ...
- 618
5
votes
6
answers
2k
views
practical algorithms for np complete problems
Inspired by:
Conjecture on NP-completeness of tesselation of Wang Tile up to finite size
And the practicality of this topic (solving tessellation on a lattice):
coloring in lattice
Computational ...
- 867
25
votes
2
answers
2k
views
An Interesting Optimization Problem
You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
- 363
110
votes
10
answers
15k
views
Analogues of P vs. NP in the history of mathematics
Recently I wrote a blog post entitled "The Scientific Case for P≠NP". The argument I tried to articulate there is that there seems to be an "invisible electric fence" separating the problems in P ...
4
votes
3
answers
405
views
powers in strings
I have a feeling that the following question might have been studied: Suppose I have a finite alphabet $A,$ with $|A| = n,$ and a string $S$ of length $N.$ A string can be said to contain a $k$-th ...
- 96.4k
20
votes
2
answers
1k
views
Minimum number of variables on which a multivariate polynomial depends?
Let $p:F_2^n\rightarrow F_2$ be a multivariate polynomial, let's say of degree 3. (Both the degree and the order of the field could probably be replaced by other constants without affecting this ...
- 9,823
4
votes
1
answer
439
views
Is the Kolmogorov complexity of at least one string of a given length equal to its length? [closed]
Is it true that for all strings of a given length (for any alphabet with more than one symbol), at least one has a Kolmogorov complexity equal to its length?
If the answer is Yes, is there a proof of ...
- 851
4
votes
2
answers
212
views
combinatorial and linear duality
Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\...
- 987
2
votes
1
answer
134
views
Integer point in a non-empty polytope
I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, ...
- 243
9
votes
2
answers
4k
views
How many Complexity Classes do you know?
We can read about the main complexity classes in textbooks and online in Wikipedia:
http://en.wikipedia.org/wiki/Computational_complexity_theory
However, in papers, there are a lot of important new ...
user39815
2
votes
1
answer
183
views
Is the domination number NP for non-bipartite graphs?
Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?
- 6,962
3
votes
1
answer
64
views
Complete classification of complexity classes / infinite approaching sequences
http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities
For complexity as seen in the above link, complexity classes can be log, polynomial, exp, or composition of any of these ...
- 31
1
vote
0
answers
75
views
Are there any known bounds on the value of solutions of linear integer programming?
Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints?
...
- 111
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
1
vote
1
answer
321
views
Cycles of Permutation Related to Rectangular Matrix Transposition
let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...
- 13.2k
1
vote
1
answer
4k
views
Maximizing linear objective function with absolute values
This has be asked on other forums, though couldn't
find authoritative answer.
I have a linear program over the reals and don't
want to introduce integer or binary variables.
The objective function ...
- 25.4k
7
votes
0
answers
252
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 "...
- 82.7k
2
votes
2
answers
841
views
Finding the maximum of a multivariate polynomial of degree one
I need to find the global maximum of the function
\begin{align}
f\left(x\right) & = p_1 \max\left(\sum a_{1i} x_{1i}, \sum b_{1i} x_{1i}\right) - \sum c_{1i} x_{1i} \\
&+\ldots \\
&+ p_n ...
user24451
8
votes
1
answer
418
views
A combinatorial problem concerned with logic circuits
Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that ...
user3409
3
votes
2
answers
418
views
Making a graph claw-free by adding as few edges as possible
Independent set is polynomial in claw-free graphs,
so I am wondering if this can approximate independent set.
By adding enough edges to $G$ and gets claw-free $G'$.
IS in $G'$ is IS in $G$, so this ...
- 25.4k
6
votes
2
answers
460
views
Cubic graphs decompositions
There are many interesting computational problems related to connected cubic graph decomposition. For instance, decomposition of cubic graph into a perfect matching and a connected 2-factor (NP-...
- 2,993
3
votes
0
answers
260
views
Partitioning a cubic graph into two induced cycles of equal order
I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord (...
- 2,993
11
votes
1
answer
457
views
Comparing two numbers given their factorization
I'm not an expert, but given the integer factorization of two numbers $a,b$:
$$a = p_{i_1}^{a_1}...p_{i_n}^{a_n}, \quad b = p_{j_1}^{b_1}...p_{j_m}^{b_m}$$
What is the time and space compexity of ...
- 1,602
1
vote
0
answers
493
views
Complexity of Nested Linear Optimization
My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
$$\max(\...
- 13.2k
1
vote
2
answers
218
views
Constructing Useful SAT Instances
Given a set of binary strings, all of length $s$, is it possible to construct a SAT instance with s literals that is satisfied only by those binary strings as assignments?
For example, consider the ...
- 1,601
4
votes
3
answers
1k
views
Minimax theorem on a non convex domain
A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
- 591
0
votes
1
answer
100
views
generalization from linear programming solution [closed]
I have a series of similar linear programs that depend on an input vector $a\in A$ and whose solution is an output vector $b\in B$. I can solve them individually, but this is wasteful. I suspect that ...
- 109
4
votes
2
answers
1k
views
Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field
I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...
6
votes
1
answer
1k
views
Best ranking in tournament: polynomial time algorithm?
This question was posed by my colleague Torbjörn Lundh in his paper Which Ball is the Roundest? A Suggested Tournament Stability Index, Journal of Quantitative Analysis in Sports 2(3), 2006. We have ...
- 5,492
2
votes
0
answers
123
views
What are natural examples of non-relativizable proofs? [duplicate]
As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).
Virtually all proofs seem to be relativizable, though.
What are good examples of ...
- 179
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
7
votes
1
answer
819
views
Has this generalization of a determinant (assigning multiplicities to the rows) been studied?
I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant:
Let $A$ be an $m \times n$ matrix with $m \le n$, and positive ...
- 1,509
12
votes
1
answer
686
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
5
votes
1
answer
327
views
Subsets of all Diophantine's sets
I have asked this question on math.stackexchange already:
https://math.stackexchange.com/questions/627461/subsets-of-all-diophantines-sets
Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\...
- 2,576
3
votes
1
answer
1k
views
Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector
Suppose you have a general $n$-th dimensional random Gaussian vector with probability distribution function $\mathcal{N}\left(\mathbf{x}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)$.
What is the ...
- 968
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
2
votes
0
answers
152
views
Reference Request: Properties of the Integer Factorization Polytope
The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online here:...
- 13.2k
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 ...