**1**

vote

**1**answer

179 views

### relationship between corner tile and edge tile of wang tile

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.
However, could we convert edge type of Wang Tile ...

**1**

vote

**0**answers

111 views

### Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...

**1**

vote

**1**answer

119 views

### Why can't there be a problem both in P and NPC [closed]

In this illustration, P and NPC are two disjoint set.
We know that NPC is non-empty. If P $\cap$ NPC $=\varnothing$, then there are elements in NP which are not in P. Doesn't this imply that P ...

**1**

vote

**0**answers

49 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 ...

**7**

votes

**1**answer

172 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 ...

**1**

vote

**1**answer

113 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) ?

**9**

votes

**1**answer

344 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 ...

**3**

votes

**1**answer

143 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 ...

**3**

votes

**1**answer

389 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 ...

**3**

votes

**2**answers

196 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 ...

**2**

votes

**0**answers

99 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 ...

**6**

votes

**4**answers

522 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 ...

**1**

vote

**1**answer

88 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$ ...

**5**

votes

**6**answers

740 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 ...

**1**

vote

**0**answers

80 views

### What is the time complexity of approximated SVD

Full SVD, on an m*n matrix $A$, $[U,S,V] = svd(A)$, would cost $O(m^2n + mn^2 + n^3)$ time.
But what is the time complexity if we only need the $k$ largest singular values, say, $[U_k,S_k,V_k] = ...

**71**

votes

**9**answers

8k 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 ...

**1**

vote

**0**answers

102 views

### Examples of languages that are in P and are not in CFL [closed]

Any examples of languages that are in P(polynomial time to recognize it) and are not in CFL(context-free language)?The more the better.

**4**

votes

**3**answers

333 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 ...

**16**

votes

**2**answers

439 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 ...

**4**

votes

**1**answer

113 views

### Kolmogorov complexity of at least one string (from amongst those of a given length) is equal to its length

Is it true that for all strings of a given length at least one has its Kolmogorov complexity equal to its length ?(For any alphabet with more than 1 symbol)
Is there a proof if the answer is in ...

**-6**

votes

**1**answer

162 views

### Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that $P-Q \neq 1$ and $N=P^2-Q^2$ [closed]

Given an arbitrary composite odd integer $N$, find two integers $P$ and $Q$ such that:
$P-Q \neq 1$ and $N=P^2-Q^2$
I am assuming that the best known solution to this problem runs at $O(2^{|N|})$.
...

**6**

votes

**2**answers

841 views

### How many Complexity Classes do you know?

We can get the of complexity classes from textbooks and online such as in Wiki
http://en.wikipedia.org/wiki/Computational_complexity_theory
However, in papers, there are a lot of important NEW ...

**3**

votes

**1**answer

144 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?

**3**

votes

**1**answer

47 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 ...

**7**

votes

**1**answer

412 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 ...

**1**

vote

**1**answer

115 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 ...

**7**

votes

**0**answers

181 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 ...

**8**

votes

**1**answer

340 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 ...

**3**

votes

**2**answers

215 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 ...

**4**

votes

**2**answers

241 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 ...

**3**

votes

**0**answers

137 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 ...

**11**

votes

**1**answer

237 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**

vote

**0**answers

120 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:
...

**1**

vote

**2**answers

114 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 ...

**3**

votes

**1**answer

691 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

322 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 ...

**2**

votes

**0**answers

93 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 ...

**12**

votes

**2**answers

526 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$; ...

**10**

votes

**1**answer

303 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 ...

**5**

votes

**1**answer

292 views

### Subsets of all Diophantine's sets

I have asked this question on math.stackexchange already:
http://math.stackexchange.com/questions/627461/subsets-of-all-diophantines-sets
Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable ...

**2**

votes

**1**answer

153 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 ...

**3**

votes

**3**answers

684 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, ...

**2**

votes

**0**answers

114 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 ...

**9**

votes

**5**answers

856 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 ...

**25**

votes

**10**answers

2k views

### Can We Decide Whether Small Computer Programs Halt?

The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not.
Are there some large $n$ ...

**2**

votes

**0**answers

219 views

### cyclotomic polynomials of given degree

Is there a fast algorithm to generate all cyclotomic polynomials $\Phi_n$ for which the degree of $\Phi_n$ is a fixed constant $d?$ This is obviously related to the "inverse totient" function: compute ...

**6**

votes

**0**answers

124 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 ...

**1**

vote

**1**answer

168 views

### Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...

**0**

votes

**1**answer

262 views

### When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...

**5**

votes

**0**answers

117 views

### Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...