All Questions
1,809 questions
5
votes
1
answer
269
views
Simplices in convex polytopes
This question is a direct generalization of:
Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices
Given a convex ...
- 96.4k
1
vote
0
answers
117
views
Formal Definition of Random Reducibility
What is the formal definition of Random Reducibility>
Arora/Barak is like:
"yeah, so it's kind like you take an instance of a problem, create n random instances of the problem; and if you have the ...
- 11
2
votes
0
answers
123
views
IP[poly] vs AM[poly]
I know the following:
$$IP[k] \subseteq AM[k+2]$$
Now, I also know that
$$ \\#SAT_D \in IP[poly]$$
(As shown on page 159 of Arora/Barak).
In their proof, (and the following proof of $$ TBQF \in ...
- 21
1
vote
0
answers
357
views
Is this minimization problem NP-Complete ?
We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.
...
- 209
3
votes
2
answers
2k
views
Complexity of computing derivatives
Sorry if this is too simple. This is my first question here.
Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point $...
- 33
3
votes
2
answers
5k
views
Linear program to maximize the minimum absolute value of linear functions ?
I'd like to compute
$\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$.
where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$.
Can this be solved with a linear ...
- 500
7
votes
2
answers
2k
views
Number theory and NP-complete
What are some of the natural number theory problems that are np-complete? I am looking for examples not in lattices and geometric number theory. Examples in analytic/algebraic number theory are ok.
- 800
10
votes
2
answers
418
views
Do there exist groups with word problems in arbitrary P-degrees?
This has been posted on TCS stack exchange for a while here and hasn't gotten any answers, so I'm trying again here.
It has been known for a long time that, given any r.e. Turing degree, there is a ...
- 258
1
vote
1
answer
1k
views
Knapsack Problem Specifics [closed]
(i) Are there limits on how many numbers must be in the set? { 1, 2 } or { 1, 5, 7, 8 , 9}
(ii) Are there limitations on how diverse or similar the numbers in the set can be? Coprime? Pairwise? { 1, ...
- 13
8
votes
1
answer
716
views
Finding colinear points in F_q^n
Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit.
Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let $A,...
- 47.4k
5
votes
1
answer
902
views
How much of P versus NP's difficulty stems from having to rule out the existence of Turing machines that "accidentally" solve, say, 3-SAT efficiently?
It seems like there is a sense in which a Turing machine that demonstrates P=NP could be said to "accidentally" exist. I'm wondering the extent to which the possibility of such machines is the main ...
- 505
4
votes
0
answers
369
views
Reducing factoring prime products to factoring integer products (in average-case)
My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...
- 41
6
votes
6
answers
3k
views
Circumference of Convex Shapes
Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
3
votes
0
answers
366
views
Amortized analysis of data structure via potential function
One common method for proving that a data structure supports an operation in $O(f(n))$ amortized time is to construct a potential function $\Phi: \mathcal S \rightarrow \mathbf R^{+}$, which ...
- 3,475
6
votes
1
answer
549
views
non-deterministic turing machines
I have one simple question:
There is a set, which can be decided in polynomial time by a (one-band) non-deterministic Turing Machine.
Why should there exist one (one-band) non-deterministic Turing ...
- 185
4
votes
1
answer
638
views
Proof systems and their hierarchy
Why ZFC is placed in top of the proof system hierarchy? How it can p-simulate other systems?
- 41
32
votes
2
answers
2k
views
The NP version of Matiyasevich's theorem
By Matiyasevich, for every recursively enumerable set $A$ of natural numbers there exists a polynomial $f(x_1,...,x_n)$ with integer coefficients such that for every $p\ge 0$, $f(x_1,...,x_n)=p$ has ...
user6976
4
votes
1
answer
365
views
Computing Simultaneous Hamming Neighborhood for a Set of Strings
Let $S = \lbrace s_1, s_2 \ldots s_n \rbrace$ be a set of strings each of length $k$ from an alphabet $\Sigma$, $h(s_i, s_j)$ denote the hamming distance between two strings. The simultaneous hamming ...
5
votes
0
answers
204
views
A polytope associated with the Hadamard Transform
In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in http://arxiv....
- 4,636
16
votes
3
answers
1k
views
symmetric integer matrices
Suppose I have a symmetric positive definite matrix $M$ with integer entries. I want to decide whether $M = A A^t,$ with $A$ likewise integral. I assume that decision problem is NP-complete, as is the ...
- 96.4k
3
votes
0
answers
257
views
Oracle separating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)
Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP?
Such an oracle ...
- 5,502
8
votes
0
answers
1k
views
Infinite Linear Programming
I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
- 133
7
votes
2
answers
3k
views
Conic hulls and cones
Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...
- 96.4k
23
votes
2
answers
2k
views
What is the complexity of this problem?
Recently on Dick Lipton and Ken Regan's blog there was a post about problems of intermediate complexity, that is, NP problems that are harder than P but easier than NP-complete. The main message of ...
- 29k
4
votes
1
answer
8k
views
Detection of Redundant Constraints
Suppose I pose the following query to a constraint logic programming
system:
?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3.
Are there systems that would recognize the last inequality as
...
Countably Infinite
5
votes
2
answers
584
views
Continuous Transportation Problem
Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ...
- 133
2
votes
2
answers
402
views
Maximization of a matrix product by iterative methods
This might not be very difficult, but I think I may have gotten a little confused.
Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
- 949
1
vote
0
answers
376
views
NP-complete variants of NPI problems
Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
- 2,993
13
votes
1
answer
2k
views
The hardness of computing inverse
Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input.
Are ...
user10891
14
votes
1
answer
4k
views
Kolmogorov Complexity and Proof Techniques
I'm interested in examples of theorems that employ the proof techniques that are utilized in the proof of the undecidability of Kolmogorov Complexity.
Definition:(Sipser) Let x be a binary string. ...
- 243
1
vote
1
answer
289
views
Proof that any NP problem can be reduced (in P time) to any problem in NPC?
Given the seemingly broad definition of NP, it is very interesting that one can prove that any member of NP can be reduced in polynomial time to any member of NPC. (I guess this is true by definition ...
4
votes
2
answers
922
views
Natural numbers of great kolmogorov complexity
Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, ...
- 7,853
9
votes
3
answers
2k
views
SDP Feasibility
I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...
- 505
3
votes
1
answer
365
views
Expressing >= as a boolean formula.
Given a bunch of boolean variables $a_i \in \{0, 1\}$,
I want to write a boolean formula to express $\sum_{i=1}^n a_i \geq k$.
i.e. I'm allowed to use $(, ), \wedge, \vee, \lnot$.
Now, if I allow ...
- 663
4
votes
1
answer
2k
views
solving multiple linear programming problems with the same set of constraints
Hi,
I need to solve a set of linear programs of the form:
Problem $i$: $\quad \max c_i \cdot x$ s.t. $ A x \leq b$.
The $c_i$'s are different vectors so each problem has a different objective ...
- 560
2
votes
2
answers
4k
views
Greedy approach to 0-1 Knapsack problem in specific instances
The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
- 949
0
votes
2
answers
754
views
Relation between P and FP
For a decision problem that belongs to P can we assume that the equivalent function problem belongs to FP? For example: Is 8 a primal number? Belongs to P means that Find a primal number belongs to FP?...
1
vote
2
answers
490
views
Can i achieve something better with the probabilistic turing machine in matter of space?
Let's suppose that a language $L \in \operatorname{NSPACE}(f(n))$ where $f(n) = \Omega(\log(n))$. And now let's suppose that i have a probabilistic turing machine. Can this machine run in $O(f(n))$ ...
- 45
17
votes
3
answers
6k
views
The cone of positive semidefinite matrices is self-dual? (reference needed)
I'm seeking a reference for the following fact.
The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar).
This result is relatively easy to prove, has been known for a long time,...
- 1,513
3
votes
3
answers
3k
views
p\poly and NP definitions
I have in front of me 1 definition of p\poly and one of NP.
Definition of p\poly:
L E P/poly if there exists a polynomial-time Turing machine M, a polynomial
p() and a function h mapping numbers to ...
- 45
5
votes
0
answers
682
views
Is integer factorization harder than RSA ($n=pq$) factorization? [closed]
This is a repost. I could not get a precise answer on math.SE and cstheory.SE
Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $...
- 236
2
votes
3
answers
10k
views
Worst known algorithm in terms of Big-O (more precisely Big-theta)?
Hello,
I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the ...
- 37
8
votes
2
answers
485
views
Efficient computation of the least fraction with square denominator greater than the square root of 2.
The least rational number greater than $\sqrt{2}$ that can be written as a ratio of integers $x/y$ with $y\le10^{100}$ can be found in a moment using a little Python program. Can anyone write a ...
- 6,199
0
votes
2
answers
257
views
Efficient computation of $E\left[\frac{1}{1+\sum_iX_i}\right]$ where $X_i$ is RV with Bernoulli distribution with different probabilities
Suppose we have the random variables $X_1, \ldots, X_n$ that have Bernoulli distributions with the (possibly different) probabilities $p_1, \ldots, p_n$. For example, $X_1$ = 1 with probability $p_1$ ...
- 21
1
vote
0
answers
638
views
Expected value of sum of fractions
Suppose $r$ is a set of attributes with probabilities while $p$ is a set of attributes without probabilities. For example, say that $r$ = {$a$:0.4, $b$:1.0} and $p$ = {$a$, $c$}. (Here, $a.prob = 0.4$ ...
- 21
1
vote
1
answer
234
views
Model for shipping widgets in an optimal way
I am a programmer and have the following requirement.
We are trying to figure out the optimal way to ship widgets. Below is the scenario:
We need to ship 1,000,000 widgets
We have two different size ...
- 113
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
2
votes
2
answers
687
views
Could this be a NP complete?
Given a undirected and unweighted graph G(V,E). M is a subset of vertices of V.
s is a vertex in V - M.
Find an optimal tree T of G defined as:
(1) M and s are in V(T)
(2) Distance (which is ...
- 131
4
votes
2
answers
1k
views
Set Cover:Greedy vs LP
Hi
Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?
thanks
- 239
15
votes
3
answers
4k
views
Complexity of computing matrix rank over integers
Does computing the rank of an integer matrix have complexity polynomial in the size of the input?
The Gaussian elimination algorithm is polynomial in the number of elementary operations (addition and ...
- 481