**5**

votes

**6**answers

821 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

327 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] = ...

**73**

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

112 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

337 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

453 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

118 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

175 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|})$.
...

**7**

votes

**2**answers

946 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

149 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

49 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

416 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

134 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

193 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

349 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

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

**5**

votes

**2**answers

292 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

168 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

247 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

138 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

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

**4**

votes

**2**answers

774 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

403 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

528 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

321 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

294 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

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

**4**

votes

**3**answers

1k 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

116 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

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

**26**

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

224 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

128 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

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

**1**

vote

**2**answers

366 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

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

**4**

votes

**0**answers

307 views

### About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...

**2**

votes

**0**answers

137 views

### Odds of projections of a point not on the hyperplane

Let $\mathcal{L}=\{\Bbb x\in\Bbb R^n:x_1+x_2+\dots+x_n=0\}$ be a specific hyperplane.
Let a projection of $c\in\Bbb R^n$ be $p(c)=[p_1,p_2,\dots,p_n]$ where $p_i\neq c_i\implies p_i=0$.
Let ...

**3**

votes

**2**answers

277 views

### Efficient representations of natural numbers via arithmetical expressions

A given natural number $n \in \mathbb{N}$ has many representations
as expressions mixing other natural numbers and the operators and punctuation symbols
$\{+,-,\times,/,\exp,(,)\}$, where '$\exp$' ...

**3**

votes

**1**answer

224 views

### Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph

It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard.
By Smith's theorem, ...

**1**

vote

**0**answers

275 views

### How to prove the NP-hardness of this scheduling problem? [closed]

Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations ...

**0**

votes

**1**answer

216 views

### Does this algorithm terminate in all scenarios?

Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in ...

**3**

votes

**0**answers

188 views

### Nesting big-O with big-Omega $O(g(\Omega(h(n))))$: is it $O$ for all $\Omega$ or for one $\Omega$?

I want to express the following statement about a function $f(n)$: there exists $f_\Omega\in\Omega(h(n))$ such that $f\in O(g(f_\Omega(n))$. What's the correct notation for this? Is it $f\in ...

**18**

votes

**2**answers

880 views

### Deep theorems and long proofs

I ran across this discussion by Daniel Shanks,
"Is the quadratic reciprocity law a deep theorem?."
Solved and Unsolved Problems in Number Theory. Vol. 297. AMS, 2001. p.64ff.
which made me ...

**2**

votes

**1**answer

208 views

### Are there any efficient (polynomial time) algorithms for finding if a multivariate quadratic polynomial has a root?

I know that in general, polynomial satisfiability is NP; however, I'm curious to know what work has been done on special classes of polynomials, and in particular quadratic polynomials of multiple ...

**-2**

votes

**1**answer

111 views

### “logical distance” link algorithmic complexity to statistical information [closed]

Someone mentioned what I think was referred to as 'logical distance'.
My hard drive crashed and I dont have the link anymore.
I do recall that I ran across it on this site, in response to linking ...

**2**

votes

**1**answer

115 views

### Dimension independent computational complexity of singular value decomposition

Suppose $X$ is a $m \times n$ real matrix, which has only $k$ number of nonzero elements ($k \ll mn$).
Given a vector $y$, the sparsity of $X$ allows $X y$ to be computed in $O(k)$ time
which is ...

**8**

votes

**0**answers

238 views

### Computing van Kampen diagrams

If G is a finitely presented group (with generating set X) and w is a word over X such that
w=1 in G, then the latter can be witnessed by a so called van Kampen diagram for w, which is
a planar ...

**6**

votes

**4**answers

533 views

### How long does it take to compute a class number?

I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the ...