All Questions
1,808 questions
1
vote
0
answers
145
views
Complexity of calculating the expectation of $\operatorname{Tr} h(A)$, $A$ is a random matrix
$A$ is a $d_1\times d_1$ random matrix. Given $\{g_i\}~(1\leq i\leq n)$ iid Gaussian variables, $f_{ij}(g_1,g_2,...,g_n)~(1\leq i,j\leq d_1)$ are degree-$d_2$ polynomials. And $f_{ij}\equiv f_{ji}~(\...
- 91
9
votes
1
answer
715
views
Is there a polynomial time algorithm for finding primes?
I was wondering if, given $k$, there is a deterministic polynomial time algorithm (polynomial in $k$) which finds a prime number with $k$ digits.
There is clearly a probabilistic one: just take random ...
- 69
1
vote
0
answers
94
views
Linear Program Optimal Value
If $f(A,b,c)$ is the optimal value of a linear program
$\min c.x$
subject to $A.x \leq b ; x \geq 0.$
Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
1
vote
0
answers
51
views
Hardness of an optimization problem when some variables are fixed
Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed.
With the two (related) examples, it is clear that ...
- 6,357
1
vote
0
answers
67
views
Are the lower elementary functions closed under limited recursion?
The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
- 1,782
3
votes
1
answer
214
views
NP-hardness of finding maximum of minimum element in diagonal of a matrix
For $A = \{a_{ij}\} \in R^{n\times n}$, is finding
$$
\max_{\sigma \in S_n}\min_{1 \le i \le n} a_{i,\ \sigma_i}
$$
NP-hard?
- 32.1k
2
votes
1
answer
174
views
Optimization over permutation
The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
- 5,429
13
votes
1
answer
712
views
Most computationally efficient Littlewood-Richardson rule
There are many, many different versions of the Littlewood-Richardson rule: the original characterization via Yamanouchi words, Remmel's version, a description via the Poirier-Reutenauer bialgebra, the ...
- 2,168
15
votes
1
answer
1k
views
(Very) Large numbers, Chaitin's incompletness theorem and a specific upper bound
Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>...
- 236k
1
vote
1
answer
181
views
Linear programming with "nice" matrices
Consider the following linear programming problem
\begin{array}{ll}
\text{minimize} & \mathrm 1^{\top} \mathrm x\\
\text{subject to} & v\le \mathrm A \mathrm x \le u\\
& \mathrm x \geq ...
CommunityBot
- 1
5
votes
1
answer
291
views
Minimum number of edges to remove to have low degree
I have the following problem, where $k$ is a fixed integer.
Input: Graph $G$.
Output: Minimum number of edges to remove from $G$ to obtain a graph such that every node has degree at most $k$.
Do ...
- 32.1k
2
votes
1
answer
46
views
Complexity for determining whether a given metric space is hyperconvex?
Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex?
Definition: A metric space is said to be hyperconvex if ...
- 599
1
vote
0
answers
114
views
Computing sine of gamma function [closed]
In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step?
Is there a ...
- 12.9k
2
votes
1
answer
240
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
- 7,875
1
vote
0
answers
35
views
Are there any known lower complexity bounds on solving positive semidefinite or positive semidefinite feasibility problems?
I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because ...
- 111
0
votes
0
answers
61
views
On diagonalizations over complexity classes
I am looking for the following PhD thesis, but could not find it, and all my attempts for finding it failed.
I am wondering if there is a way to get it:
On diagonalizations over complexity classes
By: ...
- 32.1k
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 5,429
0
votes
0
answers
85
views
Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points
Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$
\begin{align}
\max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
- 671
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 ...
- 13.2k
2
votes
1
answer
534
views
Modular square roots problem which is $NP$ hard
It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...
- 231
2
votes
1
answer
125
views
The counterpart of productive set with polynomial computational complexity
For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is ...
- 56
6
votes
0
answers
151
views
Complexity of continued fraction arithmetic operations
Let $A = [a_0; a_1, \dots]$ and $B = [b_0; b_1, \dots]$ be continued fractions.
Let's say that we want to compute $A+B$ or $A \cdot B$ while staying in the continued fraction representation. So, for ...
- 1,171
3
votes
1
answer
293
views
Relationship between P-noncomputable and P-random sets
$P$ means polynomial complexity.
$S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ noncomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example?
what is ...
- 3,084
-3
votes
1
answer
531
views
Counter net decidability [closed]
Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...
- 63
8
votes
1
answer
454
views
Classes of groups with polynomial time isomorphism problem
It is known that the isomorphism problem for finitely presented groups is in general undecidable. What are some classes of groups whose isomorphism problem is known to be solvable in polynomial time? (...
- 2,821
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 ...
- 128k
5
votes
0
answers
180
views
Is the matrix multiplication exponent $\omega$ independent from the choice of the base field
The matrix multiplication exponent, usually denoted by $\omega_{F}$, is the smallest real number for which any two $n\times n$ matrices over a field $F$ can be multiplied together using ${\...
- 151
4
votes
3
answers
1k
views
Minimax theorem on a non convex domain
A minimax theorem is a theorem which states that under certain conditions on $\mathcal{X}$, $\mathcal{Y}$ and $f$:
$$ \inf_{x \in \mathcal{X}}{\sup_{y \in \mathcal{Y}}{f(x,y)}} = \sup_{y \in \mathcal{...
2
votes
2
answers
235
views
Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them cover all the nodes?
Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$
a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$.
Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=...
- 21
10
votes
1
answer
518
views
Can $N!$ be computed in less than $\mathcal{O}(N)$ operations?
The standard algorithm to compute the factorial function $N!$ via repeated multiplications has complexity $\mathcal{O}(N)$, in the model in which each operation costs 1, no matter how many digits the ...
- 561
1
vote
0
answers
34
views
Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?
Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$
$$ax+by=c.$$
Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...
- 13.9k
1
vote
0
answers
101
views
On determinant and permanent of certain homotopy defined simple matrices
Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$
$$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$
hold ($per$ refers to permanent).
I. What ...
- 13.9k
1
vote
0
answers
161
views
On an optimization question
Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ ...
- 13.9k
0
votes
0
answers
304
views
A question regarding an unprovability proof
Let LA denote polynomial time arithmetic, Con_LA the equation stating the
consistency of LA, LAJ the system LA+Con_LA, and E2A double exponential time
arithmetic.
A manuscript of mine provides a proof ...
- 39.9k
0
votes
0
answers
146
views
Maximizing the norm of a sum of Hermitian matrices
Consider the following problem:
Problem: Given $n\times n$-Hermitian matrices $A_1,\dots,A_r$, find $e_1,\dots,e_r\in\{-1,1\}$ such that $\|e_1A_1+\dots+e_rA_r\|_\infty$ is maximized. Here the norm is ...
13
votes
6
answers
3k
views
A decision problem in graph coloring
It'll be great to get a pointer or answer to the following question:
What is the complexity of the following problem? Given an unweighted and undirected graph, can we have a proper (not necessarily ...
- 1,446
-1
votes
1
answer
445
views
What is wrong with the argument that zero permanent is polynomial?
This Lecture summarizes some well known facts about $\#P$ completeness of permanent.
Given a CNF formula $\phi$ on $n$ variables, they construct
matrix $A$ such that:
$$perm(A)=4^{3m} \#SAT(\phi)$$
...
CommunityBot
- 1
21
votes
2
answers
18k
views
Complexity of linear solvers vs matrix inversion
Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
1
vote
1
answer
201
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.
...
31
votes
4
answers
3k
views
Algebraic P vs. NP
I recently attended a lecture where the speaker mentioned that what he was talking about was connected to the algebraic version of the $P$ vs. $NP$ problem. Could someone explain what that means in a ...
1
vote
0
answers
223
views
Fastest algorithm for finding the closest semi-definite matrix?
Given a real-valued, symmetric matrix $A \in \mathbb{R}^{n \times n}$, I'm interested in finding the closest positive semi-definite matrix $X^*\in \mathbb{R}^{n \times n}$:
$$
X^* = \mathop{\text{...
3
votes
1
answer
730
views
Computational complexity of low rank SDP
Suppose we are given a general semidefinite program (SDP) of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{...
3
votes
2
answers
404
views
A natural problem on "cartesian union" of set families (hypergraphs). Are there NP-complete problems related to the notion of cartesian product?
I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle \cal S_i\rangle\substack{i\in I}$ and $\langle \cal S_j \...
1
vote
0
answers
61
views
Is there any lower bound for basis computation in finite Abelian groups?
Victor Shoup in this paper has given a lower bound for discrete logarithm. The algorithms that I have come across use discrete logarithms (extended discrete logarithms) to compute a basis for a finite ...
- 11
1
vote
0
answers
56
views
Over a given finite field, how many couples of matrices there are, for which their minimal polynomials are co-prime?
Let ${\mathbb F}_{q}$ be a given finite field. How many couples of $n\times n$ matrices $\left(A,B\right)$ over ${\mathbb F}_{q}$, such that $\gcd\left(\mu_{A}\left(\lambda\right),\mu_{B}\left(\lambda\...
- 21
2
votes
0
answers
221
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
- 82.6k
1
vote
2
answers
121
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
5
votes
0
answers
129
views
Finding an $\mathbb{F}_q$-point on one specific intersection of quadrics
Let $\mathbb{F}_q$ be a finite field of large characteristic and $a_1, a_2, \cdots, a_n \in \mathbb{F}_q$ be some pairwise different elements. I assume that $\sqrt{-1} \in \mathbb{F}_q$. Consider the ...
- 1,833
2
votes
3
answers
2k
views
Better tactics for removing redundant constraints than Linear Programming?
After reading:
Detection of Redundant Constraints
It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form
$$ ...
- 141
0
votes
1
answer
103
views
Constrained linear optimization problem on $C^1$
I am dealing with a problem of the form ($a<b$)
$$
\displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
