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)

1
vote
3answers
1k views

How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
2
votes
3answers
274 views

Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it. My question is as follows. Given a positive integer $k$, determine a set of properties ...
4
votes
2answers
249 views

Computational complexity of Knot polynomials

What's known about computational complexity of different types of knot invariant polynomials? For example, Evaluating Jones Polynomial is known to be #P hard. Is there any reference that surveys such ...
6
votes
3answers
589 views

computational complexity of primitive recursive functions

If we have a rewrite system for primitive recursive functions, which simplifies each term according to how the function was defined, then what is the computational complexity of this calculation? That ...
4
votes
2answers
253 views

How small can a language in NP\P be?

How small can a language in $NP$ but not in $P$ be? Of course, I don't expect a proof that there exists a language in $NP\setminus P$, so instead I'll ask: Can we rule out any of these conjectures? ...
17
votes
1answer
2k 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 ...
14
votes
3answers
498 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 ...
3
votes
1answer
249 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 ...
2
votes
2answers
544 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 ...
3
votes
1answer
233 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 ...
2
votes
1answer
123 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 ...
3
votes
1answer
123 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 ...
1
vote
1answer
476 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 ...
3
votes
0answers
171 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| ...
3
votes
1answer
125 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.
6
votes
1answer
351 views

Vertex transitive graphs

Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?
3
votes
2answers
600 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 ...
3
votes
0answers
153 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 ...
0
votes
2answers
105 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 ...
3
votes
2answers
190 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, ...
3
votes
2answers
596 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 ...
14
votes
4answers
3k views

What would be some major consequences of the inconsistency of ZFC?

I was happily surfing the arXiv, when I was jolted by the following paper: Inconsistency of the Zermelo-Fraenkel set theory with the axiom of choice and its effects on the computational complexity by ...
6
votes
1answer
583 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 ...
4
votes
1answer
443 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 ...
10
votes
2answers
483 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 ...
12
votes
1answer
572 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 ...
3
votes
1answer
217 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 ...
3
votes
2answers
517 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 ...
21
votes
4answers
978 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 ...
3
votes
1answer
195 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 ...
6
votes
1answer
318 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 ...
1
vote
0answers
217 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 ...
3
votes
1answer
160 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
votes
1answer
416 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$ $$ ...
4
votes
1answer
528 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? ...
1
vote
0answers
564 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 ...
3
votes
0answers
298 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?
3
votes
3answers
706 views

Problem regarding subsets that sum to 0

Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset ...
4
votes
1answer
624 views

Algorithmic war

No, not the war on drugs, but the game of War considered in Does War have infinite expected length? As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
1
vote
0answers
445 views

Representing vertices of a cube using linear combination of tensor product of smaller cubes

Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$. Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$) ...
0
votes
2answers
234 views

equivalence of NL Definitions

Hi, How to prove that the two definitions of the complexity class NL are equivalent. 1st definition is with a non deterministic logspace TM, and the second is with a deterministic logspace verifier ...
7
votes
2answers
332 views

Ordinals and complexity classes

What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size ...
7
votes
2answers
857 views

Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
5
votes
2answers
411 views

Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem. Inputs: A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...
2
votes
2answers
627 views

Enumerating all Hamiltonian Cycles in a Bipartite Vertex Transitive Graph

Hi everyone! This is my first post, apologies if I made any mistakes anywhere. Here goes the question: Consider all length 7 binary sequences. Let $X$ be the set of sequences with hamming weight 3 ...
1
vote
1answer
274 views

A regular n,2d graph is a good expander.

Context Reading about Expanders Setup A regular n,2d graph is generated as follows: generate d random permutations of [n] connect the edges; giving a n,2d regular graph ...
6
votes
1answer
1k views

Stochastic Matrix: Second largest eigenvalue and second largest absolute value of eigen value

Setup Let $A$ be a stochastic matrix. Let the eigenvalues of $A$ be $1 = \lambda_1 \geq \lambda_2 \geq \lambda_3 ... \geq -1$. Let $\lambda = \max_{x: x \perp 1} \frac{||Ax||}{|| x ||}$ Question: ...
2
votes
1answer
118 views

Structure of class P

Hi all, 1. Has there been any work done on trying to distinguish between different Polynomial Time Hierarchies say, O(n) vs O(n^2) problem? May be Turing Machine is too general for that. May be the ...
6
votes
2answers
375 views

Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that, $K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$. The ...
13
votes
6answers
1k views

Compressing Graphs (Kolmogorov complexity of graphs)

What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...