**2**

votes

**0**answers

134 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

268 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

193 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

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

**1**

vote

**1**answer

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

**4**

votes

**0**answers

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

**17**

votes

**2**answers

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

**3**

votes

**1**answer

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

**-3**

votes

**1**answer

98 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

102 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

208 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

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

**10**

votes

**2**answers

466 views

### How hard (P, NP, NP-hard) is it to compute Schur norms of matrices (as multipliers)?

Given a matrix $A\in M_n(\mathbb{C})$, I will denote by $||A||_\infty$ the operator norm of $A$, as seen acting on the Hilbert space $\mathbb{C}^n$. This makes $M_n(\mathbb{C})$ into a Banach space ...

**3**

votes

**2**answers

217 views

### Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$.
Given $g$ and either
$$ A = x g^ x$$
or
$$ A = x g^{x^2-1}$$
find $x$.
What is the complexity of solving this?
Is there a reduction to the discrete ...

**4**

votes

**2**answers

420 views

### Simplified knapsack problem

There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...

**3**

votes

**1**answer

169 views

### Hamiltonian circuit

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior.
Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...

**0**

votes

**1**answer

388 views

### Proof of the lower bounds of time of algorithm working [closed]

I have asked this question on math.stackexchange already: http://math.stackexchange.com/questions/515920/lower-bounds-on-the-running-time
There are some problems, when there is non-trivial lower ...

**1**

vote

**1**answer

146 views

### How to prove the NP-hardness of this set covering problem

In the Set Covering problem, we are given a ground set $U$ and a collection $S$ of subsets of $U$, where each subset is associated with a non-negative cost, the Set Cover problem asks to find a ...

**3**

votes

**2**answers

272 views

### Is There An Algorithmic Complexity Of A Random Distribution

Has anyone studied an equivalent to algorithmic complexity for probability distributions?
This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...

**1**

vote

**1**answer

550 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

**0**answers

71 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

**2**answers

421 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

**1**answer

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

**5**

votes

**5**answers

405 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

**1**answer

157 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

**0**answers

89 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

**1**answer

331 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

**1**answer

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

**2**

votes

**1**answer

128 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

**0**answers

48 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

**2**answers

410 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

**3**answers

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

**5**

votes

**0**answers

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

**2**

votes

**0**answers

124 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

**1**answer

108 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

**1**answer

182 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

**1**answer

126 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

**1**answer

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

**29**

votes

**1**answer

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

**1**answer

299 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

**0**answers

171 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

**1**answer

125 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

**1**answer

542 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

**3**answers

410 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

**1**answer

403 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

**0**answers

138 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

**1**answer

109 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

**0**answers

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

**24**

votes

**1**answer

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

**7**

votes

**1**answer

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