All Questions
1,809 questions
1
vote
1
answer
475
views
Is non-convex optimisation really in NP class?
Crossposted on Mathematics SE
I've seen in many optimisation papers the statement that general non-convex optimisation problem is NP-hard. If we assume that non-convex optimisation is in NP class, it ...
1
vote
1
answer
150
views
Counting $\mathrm{mod}\:p$ solutions of Diophantine equation in two variables taking $O(p^2)$ time
Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?
Geometrically this means we have to sort through a positive proportion of the ...
- 21
1
vote
1
answer
264
views
Could somebody suggest a way to determine if a parallelogram contains another parallelogram?
I thought of one way to do this.
Using the algorithm which determines if a point is inside a parallelogram,
one can determine if the polygon contains the point within $2N$ steps ($N=2$ for ...
- 19
1
vote
1
answer
190
views
Complexity of a Diophantine equation having $\leq1$ solutions
We are provided a single Diophantine equation
$$f(x_1,\dots,x_n)=0$$
having degree $\geq2$ and having the promise it has $\leq1$ solutions in the set $\{0,\dots,m-1\}^n$ and $t$ is the number of terms ...
- 13.9k
1
vote
3
answers
138
views
Literature request: Function that depends on a linear optimization problem [closed]
my question is about functions of the following form:
$$ f(t) = \max_{\mathbf{x}}~ \mathbf{c^T x} ~ {\rm s.t. \mathbf{Ax} +t \cdot \mathbf{a} \leq \mathbf{b}}, $$
where $\mathbf{x},\mathbf{b}, $ ...
1
vote
1
answer
131
views
Connections between algebraic semantics and computational complexity of a logic?
I'm re-posting this question from cstheory.SE hoping to have more luck.
I'm a computer scientist learning a bit about algebraic logic and I was wondering how knowing the algebraic semantics of a ...
- 121
1
vote
1
answer
308
views
Halting problem about subclass of Turing Machines
As we know, that the halting problem of Turing machines is undecidable. given some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can ...
- 3,094
1
vote
1
answer
155
views
Derive a vertex representation of a permutohedron from its linear-inequalities form
Let us define the $n$-permutohedron $P_n$ as the set of all $x\in\mathbb{Q}^n$ such that
$$\sum_{i=1}^n x_i = \binom{n{+}1}{2}\ \ \ \land\ \ \ \forall\,\text{nonempty}\ S\subsetneq\mathbb{N}_n\colon\ ...
user94257
1
vote
1
answer
332
views
Graph colouring for bounded degree graphs
I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...
- 903
1
vote
2
answers
150
views
investigating positivity/negativity of a function [closed]
I'm investigating if and how the positivity or negativity of a multivariable function can be proved. Consider $y_{1},y_{2},y_{3}\in\mathbb{R}$ and the following function
$$f\left(y_{1},y_{2},y_{3}\...
- 23
1
vote
1
answer
280
views
How to select a subset of points from a universal to minimize the distance from outside to inside?
Here is the detailed problem.
I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as
$$ d(...
- 573
1
vote
1
answer
4k
views
Maximizing linear objective function with absolute values
This has be asked on other forums, though couldn't
find authoritative answer.
I have a linear program over the reals and don't
want to introduce integer or binary variables.
The objective function ...
- 25.4k
1
vote
2
answers
444
views
Levenberg-Marquadt near the minima for non-zero-residual problems
I'm using the LM algorithm to do gradient descent in a model fitting context. I'm minimizing:
$$
c(x) = \sum ( f_i(x) - y_i )^2
$$
I'm noticing that after a few steps when I'm close to the minima, I ...
- 561
1
vote
2
answers
242
views
what method can I employ to solve this optimization problem which involves \min?
The optimization problem is:
maximize $$\min(\sum\limits_{i=1}^N \log\left(a_{1,i}+\frac{b_{1,i}}{c_{1,i}+d_{1,i}x_i}\right),\sum\limits_{i=1}^N \log\left(a_{2,i}+\frac{b_{2,i}}{c_{2,i}+d_{2,i}x_i}\...
- 764
1
vote
3
answers
5k
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 {{(1,...
- 41
1
vote
2
answers
2k
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 ...
- 11
1
vote
1
answer
1k
views
Computation for composition of polynomials
Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ ...
- 1,109
1
vote
1
answer
522
views
What are the consequences of a polynomial time algorithm for finding out if a given number is expressible as the sum of two squares?
This question is based on this question, in which it is asked if there is a polynomial time algorithm which finds out if a given number is expressible as the sum of two squares. One of the answers ...
- 829
1
vote
1
answer
98
views
How large can a subset of computable reals, whose comparison function is computable, grow?
How large can a subset of computable reals, whose comparison function is computable, grow?
For example, rational numbers are computable reals, and its comparison function is computable. As another ...
- 325
1
vote
1
answer
82
views
Do we really need degree constraints for ILP formulations of TSP problems
The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is
$$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...
- 13.2k
1
vote
1
answer
98
views
Optimality gap between a joint linear program and decoupled sub programs
Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants.
Consider the linear ...
- 1,421
1
vote
1
answer
92
views
What are the complexity classes of these problems about divisibility and coprimality?
The problems
'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?'
'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
- 13.9k
1
vote
1
answer
145
views
Complexity of solving $\sum_i A_i X B_i = C$
Is anything known about computational complexity of finding $X$ which satisfies the following matrix equation?
$$\sum_i^n A_i X B_i = C$$
With $A_i,B_i,C$ dense $d\times d$ matrices. Any literature ...
- 2,252
1
vote
2
answers
102
views
One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets
Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.
Now, is it possible to color vertices in $U$ with 3 colors ...
1
vote
1
answer
145
views
Category of finite models of a $\tau$-sentence
Let $\varphi$ be an $\tau$-sentence, we define the generalized spectrum of $\varphi$ as the class of its finite models, $$\text{GenSpec}(\varphi):=\{\mathcal{A}; \mathcal{A} \models \varphi, \lvert A\...
- 173
1
vote
1
answer
237
views
Gröbner basis via integer programming
I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...
1
vote
1
answer
80
views
Complexity to decide for permutation group if every element fixed at most $k$ points
I want to consider the following problem, which generalises the decision problem to decide if a given finite permutation group is a Frobenius group:
Given a finite permutation group in terms of its ...
- 798
1
vote
1
answer
111
views
Optimal "Generalization" of Polylines
This question is inspired by a lossy compression technique for polylines, namely to identify a subset of the points of polyline $\mathcal{P}$, whose removal yields a polyline $\mathcal{Q}$ within a ...
- 13.2k
1
vote
2
answers
83
views
Algorithm for a linear optimization problem
For the vectors $X=(x_1,\cdots, x_n),~ Y=(y_1,\cdots, y_n)$ and $\alpha=(\alpha_1,\cdots,\alpha_n),~ \beta=(\beta_1,\cdots, \beta_n)\in\mathbb R^n_+$ s.t. $\sum_{k=1}^n\alpha_k~~=~~\sum_{k=1}^n\beta_k~...
- 131
1
vote
1
answer
1k
views
convert absolute form into linear programming problem [closed]
I would like to convert this problem into a Linear Programming Problem :
$\min |x|+|y|+|z|$
subject to $x+y \leq 1$
$2x+z=3$.
The solution to this problem is given chapter and here. But I still ...
- 113
1
vote
1
answer
226
views
Complexity theory and closed form formulas in analysis
My question concerns definitions of "closed form" solutions. In hamiltonian systems this is closely related to complete integrability. In this context closed form can refers to having $(q(t),p(t))$ ...
- 982
1
vote
1
answer
273
views
Analogue break down between complexity theory and computability theory
Motivated by my post, Is there a program for theory of incompleteness in NP, much of NP-completeness theory has been heavily influenced by computability theory for which we were successful in proving ...
- 2,993
1
vote
1
answer
2k
views
Computation of extreme rays of rational polyhedral cones - Hemmecke's project and lift algorithm
I am working on an implementation of Raymond Hemmecke's algorithm for finding generating sets of cones: http://arxiv.org/abs/math/0203105
Unfortunately I am struggling to make the algorithm work on ...
- 11
1
vote
1
answer
202
views
The definition of computational complexity or complexity measure of computing reals [closed]
A real $r$ is computable if given any $i\in \mathbb{N}$, the $i$th bit can be outputed by a Turing Machine or an algorithm. So, what is computational complexity or complexity measure of computing the ...
- 3,094
1
vote
1
answer
243
views
A possible minimal aperiodic set of corner Wang Tile
From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...
- 867
1
vote
1
answer
631
views
relationship between corner tile and edge tile of wang tile
It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color.
However, could we convert edge type of Wang Tile ...
- 867
1
vote
1
answer
203
views
infinitary logic and partial fixed point logic
Is there a property definable in finite-variable infinitary logic $L^{\omega}_{\omega\infty}$ but not definable in partial fixed point logic FO(PFP) ?
- 41
1
vote
2
answers
218
views
Constructing Useful SAT Instances
Given a set of binary strings, all of length $s$, is it possible to construct a SAT instance with s literals that is satisfied only by those binary strings as assignments?
For example, consider the ...
- 1,601
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
1
vote
1
answer
235
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 ...
- 11
1
vote
2
answers
1k
views
Efficient algorithm finding 'a' solution of system of linear inequalities
I'm working on rational number field $\mathbb{Q}$.
Is there an efficient algorithm finding a solution of system of linear inequalities?
In many computer algebra systems like Sage or Maple,
there ...
- 627
1
vote
2
answers
660
views
constructing a curve dividing two sets of points
Lets assume I have two sets of points, each characterized as being "A" or "B", respectively, that are in a Euclidean plane. Theoretically these two sets are samplings from a space that has ...
- 11
1
vote
1
answer
240
views
Conditions for differentiability of minima and minimizers of linear functionals?
Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$.
For every continuous linear functional $F$ on $B$, define
$V(F)=min_{c\epsilon C} F(c)$ and
$S(F)= { \lbrace c \epsilon C :...
- 13
1
vote
2
answers
290
views
Pseudorandom Functions / Pseudorandom Permutations
I'm reading Yao's unpredictability -> pseudorandomness construction
and Goldreich/levin's pseudorandom permutation -> pseudorandom generator construction.
My question is:
is there a direct way to ...
- 13
1
vote
1
answer
9k
views
what is the difference between the revised simplex method andthe full tableu?
No to sound naive but they look like they include the same steps to me, one's just the algorithmical representation of the other. Thanks in advance.
- 111
1
vote
1
answer
107
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
1
vote
1
answer
148
views
Obstacles to computing $\pi(n)$ in $O(n^{2/3-\epsilon})$ time
Edit: Apologies, as mentioned in the comments I failed to notice the analytic algorithms that take $O(n^{1/2+\epsilon})$ time, so this question doesn’t make much sense. It’s possible there is a ...
- 1,798
1
vote
1
answer
69
views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
- 111
1
vote
1
answer
119
views
Optimization on non-convex set
Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem
$$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$
where a minimum is ...
- 11
1
vote
1
answer
202
views
Diagonally dominant matrix via rows permutation
Diagonally dominant matrices are required in many linear algebra algorithms such as the Gauss-Seidel algorithm.
Some matrices can be made diagonally dominant by permuting its rows and others cannot.
...
- 2,993