All Questions
1,809 questions
8
votes
0
answers
143
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,979
3
votes
0
answers
706
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 ...
- 167
2
votes
1
answer
132
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 ...
- 23
2
votes
1
answer
1k
views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
- 1,318
1
vote
0
answers
256
views
Equal maximum and minimum in a large-scale linear programming
For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...
- 111
10
votes
1
answer
676
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 ...
- 457
2
votes
0
answers
39
views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
- 21
2
votes
0
answers
163
views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
- 501
2
votes
1
answer
689
views
Why does the LP Formulation of the MST Problem need Topology Constraints?
I am looking for an example that demonstrates the necessity of either subtour-elimination or of connectivity constraints in the LP formulation of the MST
In the internet I only could find the LP ...
- 13.2k
4
votes
1
answer
358
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 ...
- 43
12
votes
2
answers
2k
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 ...
- 851
35
votes
1
answer
2k
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,993
1
vote
1
answer
324
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)$ ...
- 11
7
votes
0
answers
298
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 ...
- 5,502
1
vote
1
answer
160
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 ...
- 13.9k
17
votes
1
answer
874
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} d\...
- 627
0
votes
2
answers
244
views
Rewrite optimization objective
Hi,
I wanted to ask, under which conditions can one rewrite the optimization objective
$\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$
as
$\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$
I have particular ...
- 409
1
vote
1
answer
226
views
Construction of an integral point set given the set of distances, its minimal description to get a measure of its complexity and its unique identifier
Given a set of distances between every pair of points of an integral point set $P$ of $n$ points; say $D = \{{d_i}\}$.
Q1. What is the least time complexity
possible/known for recreating the
...
- 851
6
votes
3
answers
961
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$, ...
- 693
12
votes
1
answer
577
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 ...
- 29k
1
vote
2
answers
306
views
Name of operations on two vectors
Suppose we have two vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^m$.
I could define the mapping
$$
T: \mathbb{R}^n\times \mathbb{R}^m \rightarrow \mathbb{R}^{n\times m}
$$
as follows
$$
T(x,y) = ( ...
3
votes
0
answers
244
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 NP-...
- 2,993
4
votes
1
answer
158
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 ...
- 3,038
4
votes
0
answers
73
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 ...
- 41
24
votes
1
answer
1k
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
$\sum_{n=0}^{\infty}f(n)=\...
0
votes
2
answers
340
views
positive semidefiniteness: a psd matrix substracted by another rank 1 psd matrix
Given that $A$ is a positive semidefinite matrix, $x$ is a vector, $\lambda_0 \in [0, +\infty) $ is a real non-negative number. I want to know the answer to the following optimization problem.
$$
\...
- 101
2
votes
2
answers
129
views
LP constraint enconding
I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...
- 21
10
votes
1
answer
1k
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 ...
- 15.5k
1
vote
1
answer
296
views
Deducing Linear Inequalities
Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...
- 185
2
votes
1
answer
227
views
Arrangements of hyperplanes
Fix $n>0$ and $X\subseteq\mathbb{R}^n$. A function $f:X\longrightarrow\mathbb{R}$ is linear if it is of the form
$$
f(\bar{x})=a_1x_1+\ldots+a_nx_n+b
$$
for some $a_i,b\in\mathbb{R}$.
Suppose we ...
- 3,274
9
votes
1
answer
944
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 ...
- 19.7k
1
vote
1
answer
4k
views
What does "Vertex Solution" mean?
Hello!
I come across the word "vertex solution" in the context
" We can also assume that x and y are vertex solutions,so that the sequence {x,y} remains in a finite set."
Could anybody know any ...
- 13
0
votes
0
answers
104
views
Big eigenvalues of a special stochastic matrix
Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq |\lambda_2|(M)....
- 105
17
votes
0
answers
449
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 ...
- 992
1
vote
0
answers
111
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 ...
7
votes
2
answers
1k
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 ...
13
votes
4
answers
2k
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 ...
- 7,633
1
vote
1
answer
1k
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)$$
csun....
- 51
1
vote
0
answers
145
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
1
answer
292
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 https://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here.
In https://math....
- 11
14
votes
3
answers
3k
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 ...
- 26k
9
votes
1
answer
3k
views
Inverse of a totally unimodular matrix
A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$.
A totally unimodular matrix (TU matrix) is a matrix for which every square non-singular submatrix is unimodular. A ...
- 93
3
votes
1
answer
198
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 ...
- 41
5
votes
0
answers
171
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?
- 3,094
5
votes
1
answer
3k
views
Maximizing supermodular functions
I have a real supermodular objective function which I want to maximize with constraint. The constraint is on the size, like |A|=k .
I am wondering if anyone can give me more information about a ...
6
votes
2
answers
1k
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 ...
- 61
7
votes
2
answers
2k
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 ...
- 13.9k
0
votes
0
answers
79
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}
\sum_{k=1}...
- 2,966
5
votes
1
answer
475
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 ...
- 325
27
votes
0
answers
1k
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 ...
- 666