# Tagged Questions

**1**

vote

**3**answers

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

**3**answers

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

**2**answers

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

**3**answers

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

**2**answers

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

**1**answer

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

**3**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

351 views

### Vertex transitive graphs

Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?

**3**

votes

**2**answers

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

**0**answers

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

**2**answers

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

**2**answers

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

**2**answers

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

**4**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**4**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**3**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**2**answers

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

**2**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**6**answers

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