computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; ...

learn more… | top users | synonyms (1)

2
votes
1answer
59 views

What is Known about Preprocessing for Stabbing Queries?

In a concrete setting, I have the following problem: given a fixed set of simple objects (e.g. disks or, convex polygons with few vertices), I need to quickly report the objects that are hit (i.e. ...
7
votes
0answers
145 views

Is there an infinite increasing sequence of naturals for which Landau's function can be efficiently computed?

Landau's function $g(n)$ is the largest order of an element of the symmetric group $S_n$. Equivalently, $g(n)$ is the largest least common multiple (lcm) of any partition of $n$. In general $g(n)$ is ...
2
votes
1answer
418 views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or math.stackexchange. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
7
votes
0answers
403 views

Evidence that Graph Isomorphism problem is not $NP$-complete

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...
3
votes
0answers
114 views

On the computational complexity of the Hilbert polynomial of numerical semigroup rings

Let $(R, \mathfrak{m}) = k[[X^a, X^b, X^c]]$, $a<b<c$, $gcd(a, b, c) = 1$, be a semigroup ring. We have $R$ is a Cohen-Macaulay local ring of dimension one. It is well known that ...
3
votes
1answer
169 views

Sorting interleaved sorted lists

By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and ...
5
votes
1answer
178 views

Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem: $Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
2
votes
0answers
57 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 ...
1
vote
0answers
70 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 ...
-2
votes
2answers
181 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?
12
votes
1answer
557 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
1answer
89 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 ...
0
votes
0answers
43 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 ...
1
vote
0answers
134 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
0answers
101 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]$ ...
28
votes
4answers
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$ ...
2
votes
0answers
64 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
0answers
70 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
1answer
101 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
0answers
173 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
1answer
158 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. ...
0
votes
1answer
62 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
0answers
90 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 ...
4
votes
1answer
190 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 ...
8
votes
2answers
162 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 ...
2
votes
1answer
51 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 ...
0
votes
1answer
40 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 \ ...
3
votes
1answer
75 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
2answers
57 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$ ...
8
votes
1answer
207 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 ...
16
votes
2answers
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
1answer
173 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
1answer
138 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$ ...
1
vote
0answers
44 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 ...
14
votes
2answers
321 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 ...
13
votes
2answers
384 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 ...
2
votes
0answers
55 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 ...
1
vote
2answers
149 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
1answer
105 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 ...
6
votes
0answers
343 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 ...
1
vote
0answers
95 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 ...
5
votes
1answer
115 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) ...
0
votes
1answer
75 views

Generalized assignment problem with no integrality gap

Suppose I am solving the generalized assignment problem, so that I am given matrices $U$ and $W$ and a vector $c$ (all three of which have, say, positive entries), and I want to solve ...
6
votes
0answers
408 views

Any reason to believe that $NP \neq P$ is unprovable in ZFC

We know $NP \neq P$ from a lot of point of view like empirical reason,or theoretical reasons such as finite model theory or descriptive complexity.Although we find so many reasons to believe $NP \neq ...
8
votes
2answers
204 views

Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete

I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time: Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned ...
0
votes
1answer
363 views

Counterexample to Pólya's conjecture

It is known that Polya's conjecture is false and the smallest counter-example is about $10^9$. Assuming that we are searching for a counter-example not knowing that it exists. What useful information ...
1
vote
1answer
91 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 ...
5
votes
1answer
139 views

Aperiodic set of corner Wang Tile [closed]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
7
votes
2answers
919 views

Why are there so few zero-dimensional polynomial system solvers and is this because there is no real market for them?

My questions involve the quotes below from wikipedia regarding solving polynomial systems, which given the size of the market for Big Data & Predictive Analysis applications I find puzzling: ...
2
votes
3answers
227 views

How to define the input of computable function or Turing machine over real numbers

Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...