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
1answer
539 views

The smallest altitude amongst the triangles formed by points in the unit circle

Let $S$ be a finite set of points inside the unit circle. Consider all possible triangles formed by three distinct points in $S$, and among all such triangles find the smallest altitude. Denote this ...
0
votes
0answers
68 views

maximum weight k-edge problem

Given positive integer $k$ and an undirected graph $(V,E)$, with nonnegative (non-uniform) weights on the nodes. Find $k$ edges whose spanning nodes have the maximum weight. Is this in P or NP? I ...
5
votes
2answers
412 views

A simple language and systematic computations

The following somewhat popular simple computer language was enjoyed on sci.math, sci.math.research, pl.sci.matematyka, and perhaps before and after at several places (I wish I knew it's exact ...
2
votes
1answer
140 views

For interior point methods of linear programming, what is the “L” in the computational complexity $\mathcal{O}(n^3 L)$?

My question is about interior point methods of linear programming. Suppose the constraint matrix $A$ has $m$ rows and $n$ columns, and $m<n$. The state-of-the-art methods, like primal dual interior ...
0
votes
0answers
37 views

Finite window transformations--input+output (pure algebra)

This q. presents a complete approach to my previous q.: Indecomposability of image transformations ... Let $\ A\ B\ $ be finite sets of cardinality $\ > 1$.   Let $\ D:=A\times B$,   ...
5
votes
5answers
280 views

Efficient Hamiltonian cycle algorithms for graph classes

Generally speaking finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $G$ then we can reduce the finding of a Hamiltonian cycle in $G$ to a Eurler your of $H$ ...
4
votes
1answer
154 views

NP-hardness of sparsest cut

Consider bipartitioning the vertices of a graph $(V,E)$ into $V = P \cup Q$ to minimize $$\frac{|E(P,Q)|}{|P| |Q|},$$ where $E(P,Q)$ denotes the set of edges in the cut. The usual citation for ...
1
vote
0answers
88 views

Indecomposability of image transformations (pure algebra). Open questions

W-transformations -- definitions We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...
4
votes
1answer
305 views

The relationship between P vs NP problem and “Kolmogorov complexity with time”

Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$. Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?" Is it Problem1 $\in ...
13
votes
1answer
419 views

How fast can we numerically calculate Kloosterman sums?

Define the usual Kloosterman sum by $$S(m,n;c) = \sum_{\substack{x \pmod{c} \\ (x,c) = 1}} e\Big(\frac{mx + n\overline{x}}{c}\Big),$$ where $x \overline{x} \equiv 1 \pmod{c}$, and $e(x) = e^{2 \pi i ...
0
votes
0answers
133 views

k-means type clustering of binary data, under capacity constraints per cluster. Proof of NP-hardness?

Suppose you are given a set of $I$ binary vectors in ${\mathbb R}^N$, a number of clusters $k$, and positive integers $\{ c_i \}_{i=1}^k$ where $\sum_{i=1}^k c_i = I$. I am interested in finding a ...
2
votes
1answer
122 views

Complexity of numerically solving systems over the reals

Basically I am interested in What is the complexity of numerically solving systems over $\mathbb{R}$? By solving I mean finding at least one numeric solution with given precision. Probably the ...
1
vote
0answers
46 views

A criterion or algorithm for polynomial which admits Markov partition on its Julia set

For a given polynomials $P(z)$, whether there exists general algorithm to check it admits a Markov partition on its Julia sets. (in finite computation time.) May be it is more difficult for the ...
10
votes
2answers
353 views

What Turing-Complete models of computation carry a notion of time complexity that “agrees” with that of Turing Machines?

Certain models of computation are technically Turing-Complete, but cannot feasibly simulate a Turing Machine within the usual time constraints we hope for. One example of this is Godel's recursive ...
1
vote
3answers
140 views

unbounded complexity

If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ? For example what would be the complexity class of the language of "provably halting ...
4
votes
0answers
75 views

Can the isomorphism relation for countable models become harder when adding finitely many constants?

I am particularly interesting in the case where $T$ is o-minimal, but I would be interested in any theory $T$ (or even an $L_{\omega_1,\omega}$-sentence) which has this property. Context: view the ...
1
vote
0answers
101 views

Row subset selection of matrix to optimize condition number

Given a matrix $\mathbf{A} \in \mathbb{C}^{N\times M}$ with $N \gg M$. This matrix results from a linear equation system and has a certain structure (however, I do not think that details provide any ...
2
votes
1answer
105 views

Computation of the mean of a random variable to estimate algorithm complexity

I made an incremental algorithm which I would like to evaluate the complexity. The algorithm works with a sliding window of size n. To study the complexity, the window is considered full and the data ...
9
votes
1answer
158 views

How hard is Heyting satisfiability, i.e. the constructive version of SAT? In particular, is 2-HSAT NL-complete or is it harder?

First of all, is it clear what I mean by $k$-HSAT? I'm assuming that for $k>2$, $k$-HSAT is NP-complete, but the details of the reductions between $k$-HSAT and $k$-SAT aren't obvious to me. I'm ...
2
votes
1answer
112 views

$\mu$-recursive definitions for the complexity classes P, NP, etc

The standard complexity classes such as P, NP are usually defined using Turing Machines. In finite model theory those classes can be defined via the classical first-order/second-order logics. I am ...
8
votes
1answer
208 views

Fold-and-cut problem in three dimensions

The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...
20
votes
1answer
758 views

How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
2
votes
1answer
295 views

Problem to a solution

Consider an NP hard problem $\frak P$ which takes an input of length n $\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...
5
votes
0answers
148 views

Feasible Type Theories

I am looking for references about efficient type theories, efficiency in the sense of computational complexity, and type theory in the sense of Martin-Lof's type theories. Has there been any studies ...
1
vote
1answer
120 views

Finding reducible polynomials with restricted factors

Given $f(x),g(x) \in \mathbb{Z}[x]$, two irreducible polynomials, is there a polynomial $h(x) \in \mathbb{Z}[x]$ coprime to $f(x)$ such that $f(x) + g(x)h(x)$ is reducible over $\mathbb{Z}[x]$ with ...
17
votes
1answer
515 views

An NP-hard $n$ fold integral

We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$. Consider the $n$-fold integral $$ J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} ...
4
votes
3answers
365 views

What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?

Let me begin with an example. Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...
11
votes
1answer
379 views

Are there very strongly pseudorandom permutations?

A pseudorandom permutation can be defined formally as a function $\phi$ from $\{0,1\}^k\times\{0,1\}^n$ to $\{0,1\}^n$ such that for every $x\in\{0,1\}^k$ the function $\phi_x:y\mapsto\phi(x,y)$ is a ...
2
votes
0answers
119 views

Intermediate $\mathsf{NP}$-complete problems?

Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition problem is strongly ...
4
votes
1answer
102 views

About infinite subset of halting probability and 1-random set

Let $\Omega$ be the halting probability (see (http://en.wikipedia.org/wiki/Chaitin's_constant) and R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity for reference). If A is ...
2
votes
0answers
52 views

Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
23
votes
1answer
675 views

Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether ...
6
votes
1answer
369 views

Can we invert barycentric subdivision?

With apologies to fellow algebraic topologists, I confess that I have no idea how to answer this innocent-looking question: (1) Let's say we know that a finite simplicial complex $S$ is the ...
7
votes
1answer
420 views

Normality of Chaitin's constant

Can anyone provide an overview of the proof that Chaitin's constant is normal, or better yet, the guiding intuition? Even if we replace the existential quantifiers in the assertion of non-normality ...
11
votes
0answers
296 views

Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but: Question: Is there a reformulation of the Dynamic ...
1
vote
0answers
92 views

Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
4
votes
2answers
217 views

Hardness of approximation of Dominating Set

It is stated throughout the computational complexity literature that the Dominating Set problem is NP-hard to approximate within a factor of $\Omega(\log n)$. To my knowledge, the first and only proof ...
10
votes
4answers
719 views

Quantum algorithms for dummies

I want to try my hand at designing quantum algorithms to solve certain problems. I feel like I understand (for example) how Grover's algorithm and Shor's algorithm work, and I'm excited to apply the ...
1
vote
1answer
175 views

Longest run of heads

Consider $n$ independent tosses of a fair coin; the sample space has $2^n$ elements. Let $R_n(x)$ be the length of the longest run of heads in outcome $x$. We know that $$E[R_n]=\Theta (\log n)$$ ...
1
vote
0answers
69 views

Are set covering problems with nonlinear cost functions NP-Hard?

Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this? To be more specific the cost function I am interested in ...
1
vote
1answer
152 views

Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

I failed to get an answer at http://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here. In ...
11
votes
3answers
1k views

Will quantum computing kill cryptography ? [closed]

I apologize as this question is not really mathematical, and therefore perhaps not well-suited for this site. Please feel free to close it if you think it is not. My reason for asking it here is that ...
1
vote
1answer
103 views

Separation of Anti-Hole Inequality

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent. An induced subgraph $H$ of $G$ is called an odd-antihole ...
5
votes
0answers
116 views

Computational complexity of resolution of singularities of varieties over fields with characteristic 0 [closed]

What is the computational complexity of resolution of singularities of varieties over fields with characteristics 0?
6
votes
2answers
720 views

Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...
6
votes
2answers
477 views

Strassen's algorithm

I am reading Landsberg's "Tensors: Geometry and Applications". Here he mentions tensor formulation of Strassen's algorithm and shows that the rank of Strassen's matrix multiplication tensor is $7$ and ...
0
votes
0answers
56 views

Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\{1,\ldots,m\}$, I want to maximize the quantity \begin{equation} ...
4
votes
1answer
248 views

Maximal chain of 1s in binary strings

Let $S$ be the set of $2^n$ binary $n$-bit strings. For every $x\in S$, let $f(x)$ is the maximal chain of bits 1 in $x$. So Can we find a good upper bound of $$F(n)=\frac{\sum_{x\in S}f(x)}{2^n}$$ Of ...
17
votes
0answers
410 views

Computational complexity of topological K-theory

I am a novice with K-theory trying to understand what is and what is not possible. Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with ...
1
vote
1answer
219 views

definition of NP [closed]

"Popular" discussions of PvsNP often begin by characterizing NP problems as those for which a purported solution can be verified in polynomial "time". Later the definition changes to; the problem is ...