computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; ...

learn more… | top users | synonyms (1)

5
votes
6answers
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
0answers
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
9answers
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
0answers
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
3answers
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
2answers
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
1answer
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
0answers
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
2answers
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
2answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
3answers
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
0answers
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
5answers
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
10answers
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
0answers
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
0answers
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
1answer
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
2answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
4answers
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 ...