**2**

votes

**0**answers

50 views

### Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from ...

**2**

votes

**1**answer

588 views

### Efficient algorithms to determine the roots of: $p(x) = r^x $ in the finite field $GF(q)$, where $r$ a primitive root of the field

I need to make sure that no efficient (i.e., polynomial time) algorithm exists for the following problem:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq ...

**17**

votes

**5**answers

2k views

### Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.
When I learnt to the topic of relativization ...

**1**

vote

**0**answers

42 views

### Reducing enumeration of reduced words in general Coxeter groups to another #P-complete problem

There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words ...

**10**

votes

**1**answer

690 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time.
...

**-2**

votes

**2**answers

164 views

### Time estimate to determine if a number is prime [closed]

How long does it take to verify that a given number is a prime number, as a function of its number of digits, in a personal computer, say? How computationally hard is this?

**11**

votes

**1**answer

477 views

### Is there a known primitive recursive upper bound on the nth “Zhang prime”

(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...

**3**

votes

**1**answer

74 views

### What is Known About the Complexity of Calculating Minimal Surface Polyhedra?

I am currently ruminating about ways of generalizing Minimum Spanning Trees to Minimum Spanning "Hypertrees", where the cost is associated with simplex volumes and, where certain topological ...

**14**

votes

**4**answers

2k views

### Zero-knowledge proof of positivity

If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?
My bounty is ending ...

**0**

votes

**0**answers

117 views

### NP-completeness of Ising model [migrated]

In this paper:
http://www.brown.edu/Research/Istrail_Lab/papers/p87-istrail.pdf
It is claimed that calculating partition function of 3 dimensional ising model is NP-complete. But I have a question, ...

**1**

vote

**1**answer

104 views

### Cycles of Permutation Related to Rectangular Matrix Transposition

let the entries of a rectangular matrix $A\in\mathbb{C}^{m\times n}; m,n\in\mathbb{N}$ be stored in row-order in a linear vector $v$, i.e. $A_{i,j}=v_{i*m+j}$
Question:
How can the first element ...

**0**

votes

**1**answer

224 views

### When is a power of an indeterminate in an ideal with 2 generators?

If I have an ideal ${\frak a} \colon= (f(X,S), g(X,S))$ of height $2$ in ${\Bbb C}[X, S]$, is it easy to know what power of $S$ is contained in $\frak a$? For example, what is the minimal number $m$? ...

**0**

votes

**0**answers

34 views

### Is there any SMT solver which allows a call to another SMT solver?

I have a problem to solve which is likely to be $\mathbf{NP}^{\mathbf{NP}}$-hard. That is, I could solve it if I could take advantage of an instruction such as "assert UNSAT using ...

**26**

votes

**4**answers

3k views

### Massive cancellations

Let $A=\{a_1,\ldots,a_k\}$ be a fixed, finite set of reals. Let $S_A(n)$ be the set of all reals that are expressible as the sum of at most $2^n$ terms, where each term is a product of at most $n$ ...

**1**

vote

**0**answers

72 views

### NP hard problems on geometric graphs

I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...

**2**

votes

**0**answers

92 views

### counting irreducible factors

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer.
Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ ...

**9**

votes

**2**answers

981 views

### How to determine if there exists a non-zero vector in the kernel

If you are given a $0$-$1$ circulant matrix with $n$ rows and $n$ columns, is there an efficient way of determining if there exists a non-zero $\{-1,0,1\}$-vector in its kernel?
Could this problem ...

**2**

votes

**0**answers

49 views

### relationship of max-sat and min-cut in theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model:
For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...

**2**

votes

**0**answers

63 views

### What is the computational complexity to compute the integral numerically?

Given $$\int_{\Delta}\frac{P_1(x_1,x_2,\dots,x_n)}{P_2(x_1,x_2,\dots,x_n)}$$ where $P_i$ is polynomial(that is $P_1(x_1,x_2,\dots,x_n), P_2(x_1,x_2,\dots,x_n)$ are polynomial) whose coefficients are ...

**-2**

votes

**1**answer

86 views

### how to reduce 3-colorable graph to this? [closed]

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...

**0**

votes

**1**answer

33 views

### Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ ...

**0**

votes

**0**answers

59 views

### Prove that the subset sum problem with fixed size and number reusability is NP complete

I'm trying to solve the following problem:
There are B lists of unspecified size containing integers. Pick a number from each list so that the sum of all the picks is exactly A. Prove that this ...

**1**

vote

**1**answer

122 views

### NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard.
...

**4**

votes

**1**answer

128 views

### The Universality Theorem by Mnev for uniform oriented matroids of rank 4 and higher

According to the Universality Theorem by Mnev (see below theorem 8.6.6 from [1]), for any open semialgebraic variety V there is a uniform oriented matroid of rank 3 whose realization space is stably ...

**3**

votes

**3**answers

533 views

### Can you efficiently solve a system of quadratic multivariate polynomials?

Given a system of 2nd-degree polynomials, $P=\{p_1,\dots,p_m\}$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R}$, can you efficiently find a common zero of all of these polynomials? In other words, ...

**0**

votes

**1**answer

55 views

### Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?

**6**

votes

**0**answers

89 views

### Checking if a multiplication table represents a group [duplicate]

Given an $n \times n$ multiplication table,
can one check if it represents a group in $o(n^3)$ time?
All properties can be checked by mindless try-all possibilities loops:
Whether there is an ...

**8**

votes

**2**answers

158 views

### Polynomial-time algorithm for determining whether a polynomial is positive on $\mathbb{N}$

Does there exist a polynomial-time algorithm to determine whether a given polynomial $p(n)$ with integer coefficients is positive on $\mathbb{N}$, in the sense that $p(n) \geq 0$ for all ...

**7**

votes

**1**answer

149 views

### Can Schwartz-Zippel be formulated for commutative rings instead of fields?

The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for ...

**2**

votes

**1**answer

49 views

### Length preserving rewriting system with NP-complete $u\to v$ problem

My question is related to Computational complexity of the word problem for semi-Thue systems with certain restrictions.
Is there a finite length-preserving string rewriting system $R$ (over say ...

**3**

votes

**1**answer

59 views

### The link and equivalence between variant definition of computation model and computational complexity over reals

To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...

**2**

votes

**2**answers

51 views

### Deciding whether a given graph has an f-factor or not!

Given a graph $G$ with $n$ vertices and a function $f$ from $\{1,2,...,n\}$ to non-negative integers, Does there exist an efficient (for example polynomial time) algorithm, that decides whether $G$ ...

**14**

votes

**2**answers

1k views

### “a shape that … lies halfway between a square and a circle”

An article in the
Notices of the AMS, Volume 61, Issue 10, 2014
(PDF download link),
on Khot's Unique Games Conjecture, says this:
Another group ... found a
shape that in a certain sense lies ...

**1**

vote

**1**answer

170 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**

votes

**1**answer

103 views

### Existence of subgraphs when given its degree sequence

For a given simple graph $G$ with $n$ vertices $v_1,v_2,\dots v_n$, the corresponding degree sequence is $d_1,d_2,\cdots,d_n$. My qusetion is:
How to determine whether there exist subgraphs in $G$ ...

**26**

votes

**1**answer

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

**14**

votes

**2**answers

300 views

### Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by ...

**1**

vote

**3**answers

2k views

### Determining the space complexity of van Emde Boas trees

We call S(u) the space complexity of the vEB tree holding elements in the range 0 to u-1, and suppose without loss of generality that u is of the form 22k.
It's easy to get the recurrence S(u2) = ...

**1**

vote

**0**answers

38 views

### Recognizing bridgeless cubic graph with special 2-factor

A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a perfect matching).
I conjecture ...

**35**

votes

**3**answers

4k views

### Testing whether an integer is the sum of two squares

Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer $n$ is a sum of two squares?
By "fast" here I mean polynomial time (i.e. time $O((log n)^{O(1)})$). Note ...

**5**

votes

**2**answers

338 views

### Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...

**13**

votes

**2**answers

375 views

### What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$

Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...

**6**

votes

**0**answers

272 views

### Is simultaneous diophantine approximation (in a weaker sense) NP hard?

The traditional problem of simultaneous diophantine approximation is: Given a set of rational numbers $g_1,\ldots,g_d$, an integer $N$, and a rational $\gamma>0$, is there an integer $W$ with ...

**2**

votes

**0**answers

50 views

### Computing basis of a lower set given basis of complementary upper set

In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest ...

**12**

votes

**2**answers

523 views

### Faster multiplication with a restricted set of multiplicands?

Let $A$ be a set of $k>1$ distinct elements from a semigroup. We wish to compute the product
$$ p=b_1 b_2 \cdots b_n$$
where each $b_i\in A$.
Clearly $n-1$ multiplications suffice to compute $p$; ...

**1**

vote

**2**answers

133 views

### Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity.
...

**2**

votes

**1**answer

101 views

### enumeration of connected blocks in finite size square

Given a square of size n by m, how many ways could we choose sites, such that all the sites are connected?
By "connected" we mean "connected" by adjacent sites. We will illustrate by example, say, we ...

**5**

votes

**1**answer

109 views

### What is the (mixed strategies) equilibrium of this game?

Given a weight vector $w\in [0,1]^d$ such that $\sum w_i=1$, the game goes as follows:
Two players, $X,Y$ choose strategies $x,y\in [0,1]^d$ such that $\sum x_i = \sum y_i = 1$.
The utility (profit) ...

**1**

vote

**0**answers

48 views

### Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here.
I want to know the optimal complexity of an algorithm (I mean the ...

**2**

votes

**0**answers

184 views

### Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
...