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
0answers
88 views

reference on aperiodicity and cluster [on hold]

From this image: I believe there is a message relating those clusters drawn in picture and aperiodic tiling. Does anyone have some reference on this? Thank you :)
0
votes
0answers
93 views

Any result, example or conjecture about the computational complexity of transcendental number that can not be computed by linear time Turing Machine [on hold]

The Hartmanis-Stearns Conjecture is restated by Prof.Lipton as: Suppose that a linear time Turing Machine computes the first $n$ digits of the real number $r$ in base ten. Then, the number is either a ...
0
votes
1answer
333 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 ...
2
votes
3answers
161 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 ...
2
votes
1answer
474 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 ...
2
votes
1answer
47 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 ...
6
votes
1answer
94 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
826 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: ...
10
votes
1answer
586 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. ...
10
votes
1answer
358 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$; ...
2
votes
0answers
115 views

NP-hard proof of optimization version of exact cover [closed]

Exact cover is NPC. http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems Given a collection $\mathcal{S}$ of subsets of a set $X$, an exact cover is a >>subcollection $\mathcal{S}^*$ ...
4
votes
1answer
225 views

If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well?

This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define ...
0
votes
1answer
158 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$? ...
2
votes
0answers
75 views

Existence of roots of high order polynomial over finite fields

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
4
votes
2answers
2k views

Computational complexity of calculating the nth root of a real number

Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example: Jean-Michel Muller, "Elementary Functions: ...
0
votes
1answer
121 views

Function that dominates everything in little o

I have a function $f(n)$ that satisfies the following property: for any function $g(n) = o(n^{-2})$, we have $f(n) = \Omega(g(n))$ (the implied proportionality constant in the $\Omega$ expression ...
3
votes
1answer
209 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ ...
2
votes
0answers
161 views

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
7
votes
1answer
219 views

Compute an arbitrary decimal place of $\pi$

Is there a method to find the value of the $n$-th decimal place of $\pi$ which is more efficient than having to compute all decimal places before as well?
3
votes
0answers
142 views

Both NP-hard but different [closed]

What's the fundamental difference between the Knapsack problem and the travelling salesman (TSP) problem both of which are NP-hard, while the reality is that TSP could be solved much much faster?
0
votes
0answers
40 views

Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs. What is the complexity of graph isomorphism in $(P_4 ...
3
votes
1answer
164 views

Hamiltonian circuit

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior. Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...
1
vote
1answer
74 views

A certain instance of the Set Covering problem

Is there any useful structure associated with the following instance of the Set Covering problem? Let $G$ be a weighted graph and let $\mathcal{P}$ denote the set of all shortest paths between all ...
1
vote
1answer
55 views

Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs

Nisan's answer to this question shows the Impossibility of efficient sampling from random non-Hamiltonian graphs (unless $NP=coNP$). I am interested in the implications of this conjecture. Does ...
5
votes
2answers
192 views

Generating Hard Instances

Assume NP$\neq$P and let $L$ be an NP-complete language. Is there a polynomial time computable function $f:\{0\}^*\longrightarrow\{0,1\}^*$ with $|f(0^n)|=n$ for every $n$; such that L $=\{0^n: ...
33
votes
6answers
2k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
-3
votes
1answer
179 views

are all NP problems made up of P problems? [closed]

are all NP problems made up of P problems? that is, can NP problems be thought of as an accumulation of P problems? or can NP problems be divided up into a series of P problems?
1
vote
0answers
50 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there graph problems that can be solved in ...
0
votes
0answers
79 views

Resources about integral maximization problem

I am looking at the following problem. Given an interval I, and a function f over that interval, find sub-intervals for which: The sum of the length of the sub-intervals is < k; The sub-intervals ...
1
vote
0answers
139 views

Is finding a single vector in the null space as difficult as discovering the whole null space?

Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is: Is the ...
7
votes
1answer
463 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 ...
13
votes
1answer
594 views

Who first dubbed them “expander graphs”?

Expander graphs ("sparse graphs that have strong connectivity properties") burst onto the mathematical scene around the millennium, but I have not been successful in tracing the origin of (a) the ...
3
votes
3answers
735 views

An established proof in Wang Tile which I doubt

When I was reading the paper: Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305. from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf I could not ...
1
vote
0answers
62 views

What is the generic complexity of First Order Predicate Calculus?

I suspect that it should be the same as that of the Turing machine halting problem, which wikipedia gives as GenP and attributes this result to Hamkins and Miasnikov, but I am not sure. Is the generic ...
7
votes
1answer
517 views

Can the Legendre symbol be calculated in polynomial time?

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...
10
votes
2answers
439 views

How hard (P, NP, NP-hard) is it to compute Schur norms of matrices (as multipliers)?

Given a matrix $A\in M_n(\mathbb{C})$, I will denote by $||A||_\infty$ the operator norm of $A$, as seen acting on the Hilbert space $\mathbb{C}^n$. This makes $M_n(\mathbb{C})$ into a Banach space ...
0
votes
0answers
31 views

two model-checking problems on nondeterministic finite automata: are they in $\mathsf{P}$?

Let us consider a slight modification of a nondeterministic finite automaton, let us name it a "weighted nondeterministic finite automaton" $\mathcal{A}$ which is a tuple $(Q, \Sigma, \Delta, q_0, ...
2
votes
1answer
103 views

QBF of exponential length?

We consider a slightly extended version of a nondeterministic finite automaton, call it a "propositional nondeterministic finite automaton". It is defined as follows. Consider a fixed propositional ...
1
vote
1answer
35 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 $$ ...
5
votes
0answers
119 views

Computational complexity of resolution of singularities of varieties over fields with characteristic 0 [closed]

What is the computational complexity of resolution of singularities of varieties over fields with characteristics 0?
23
votes
1answer
709 views

How strong is this conjecture? $(Z/nZ)^*$ is generated by “small” elements

Conjecture: There are constants $c,k$ such that every $(Z/nZ)^*$ is generated by its elements smaller than $k (\log n)^c$. Where $(Z/nZ)^*$ is the multiplicative group of integers mod $n$. My ...
4
votes
2answers
186 views

Conjecture of a subset of Wang tile which might be decidable

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature: The left color and ...
4
votes
3answers
371 views

What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?

Let me begin with an example. Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...
3
votes
0answers
119 views

characterization of all periodic tiling of a simple set of Wang Tile

Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set. Now, I wish to characterize all the periodic tilings of this set (better if they are ...
2
votes
0answers
102 views

Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
2
votes
1answer
90 views

simple cycle analog in 2D (with application in tiling)

We know that any closed cycle of a graph could be decomposed into sum of simple cycles. To translate this theorem into tiling of 1D (Wang tile). We know that any 1D periodic tiling could be ...
1
vote
0answers
121 views

Basis of periodic tiling of Wang tile

Given a set of Wang tile, Given 3 periodic tiling: A, B, C We define 3 vector F[A], F[B], F[C] each vector correspond to the appearing frequency of each type of tiles in the tiling. Now, we ...
1
vote
2answers
240 views

Computational complexity of solution of Pell equation and more

What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity? And more,could ...
1
vote
1answer
179 views

Longest run of heads

Consider $n$ independent tosses of a fair coin; the sample space has $2^n$ elements. Let $R_n(x)$ be the length of the longest run of heads in outcome $x$. We know that $$E[R_n]=\Theta (\log n)$$ ...
2
votes
1answer
145 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 ...