**1**

vote

**1**answer

107 views

### Separation of Anti-Hole Inequality

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent.
An induced subgraph $H$ of $G$ is called an odd-antihole ...

**5**

votes

**0**answers

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?

**6**

votes

**2**answers

726 views

### Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...

**6**

votes

**2**answers

480 views

### Strassen's algorithm

I am reading Landsberg's "Tensors: Geometry and Applications". Here he mentions tensor formulation of Strassen's algorithm and shows that the rank of Strassen's matrix multiplication tensor is $7$ and ...

**0**

votes

**0**answers

56 views

### Approximation for accumulative set cover

Let $S_1,\ldots,S_m\subseteq U$ be subsets of a set $U$ of size $\lvert U\rvert=n$. Over all permutations $\pi$ of the set $\{1,\ldots,m\}$, I want to maximize the quantity
\begin{equation}
...

**4**

votes

**1**answer

248 views

### Maximal chain of 1s in binary strings

Let $S$ be the set of $2^n$ binary $n$-bit strings. For every $x\in S$, let $f(x)$ is the maximal chain of bits 1 in $x$. So Can we find a good upper bound of $$F(n)=\frac{\sum_{x\in S}f(x)}{2^n}$$
Of ...

**17**

votes

**0**answers

417 views

### Computational complexity of topological K-theory

I am a novice with K-theory trying to understand what is and what is not possible.
Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with ...

**1**

vote

**1**answer

220 views

### definition of NP [closed]

"Popular" discussions of PvsNP often begin by characterizing NP problems as those for which a purported solution can be verified in polynomial "time". Later the definition changes to; the problem is ...

**3**

votes

**1**answer

196 views

### The existential theory of the reals

Some definitions of the existential theory of the reals (ETR) allow a real closed field and some definitions allow only rational numbers as coefficients of polynomials. Which one is correct? Will the ...

**2**

votes

**2**answers

128 views

### Size-limited oracles

I am interested in complexity of algorithms which have access to the following peculiar sort of oracle:
Suppose that an invocation of an algorithm f with an input of size n has access to an oracle ...

**6**

votes

**0**answers

245 views

### Is integer GCD in NC?

Wikipedia, in the page http://en.wikipedia.org/wiki/Greatest_common_divisor#Complexity mentions integer GCD is in NC by citing http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci07.pdf
...

**1**

vote

**2**answers

111 views

### complexity of finding optimal matchings of given fixed size

It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...

**6**

votes

**1**answer

233 views

### Do sparse DAGs can have large min-cuts?

For a graph $G$, let $e(G)$ denote the number of its edges, and $c_k(G)$ the smallest number
of edges that must be removed in order to destroy all paths of length $\geq k+1$.
Note that $c_1(G)\geq ...

**16**

votes

**1**answer

560 views

### Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...

**1**

vote

**0**answers

128 views

### NP problem implications [closed]

Hi, i would like to have some clarification on NP-completeness.
In particular I'm reading an article where they show:
1) Partitioning the edges of a graph into connected component of 3 edges (3-path ...

**4**

votes

**1**answer

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

**8**

votes

**1**answer

360 views

### computational complexity

I am interested into computational complexity of decision problem: Does a given 2-dimensional simplicial complex contain (any)triangulation of 2-sphere? This problem trivially lies into NP, because ...

**9**

votes

**6**answers

1k views

### Non-constructive proofs vs. efficient algorithms

My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof begins, "a constructive ...

**5**

votes

**0**answers

106 views

### Are there sampNP-intermediate problems?

This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} ...

**6**

votes

**1**answer

240 views

### How do you compute the primes of bad reduction?

Suppose that I am given a subscheme $Y$ of $\mathbf{P}^n_{\mathbf{Z}}$, flat over $\operatorname{Spec}\mathbf{Z}$ and with smooth generic fiber $Y_{\mathbf{Q}}$, defined by the vanishing of some ...

**4**

votes

**1**answer

363 views

### Exact arithmetic for real algebraic numbers

There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms
in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...

**12**

votes

**6**answers

1k views

### SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...

**1**

vote

**1**answer

287 views

### Non-uniform complexity of the halting problem

This question is approximately cross-posted from Theoretical Computer Science Stack Exchange: http://cstheory.stackexchange.com/questions/14445/complexity-of-the-halting-problem
What can be said ...

**2**

votes

**1**answer

231 views

### If NP=EXPTIME, does every DTM have a succinct “execution proof”?

Let HALTS-IN-N be the canonical $EXPTIME$-complete language {<$M$,$n$> | the deterministic Turing machine (DTM) encoded by $M$ halts in $n$ or fewer steps, with $n$ encoded in binary}. Since ...

**3**

votes

**2**answers

96 views

### How would one characterize a PR-complete language?

The complexity class $PR$ is the set of all formal languages that can be decided by a primitive recursive function. Is there any language $l$ known to be complete for this class, i.e., for every ...

**3**

votes

**1**answer

142 views

### fast approximate k-nearest neighbors in high dimensions?

Hi, I've been scanning the literature trying to find an adequate approximate k-neighbour for my outlandish data set, but I remain stymied. Perhaps someone can help?
The dataset is huge, both in ...

**7**

votes

**3**answers

798 views

### shallow question: Why a 300 digit number is associated with “any NP-hard problem”?

I was reading this article (http://www.ams.org/notices/200203/fea-knuth.pdf) the other day and noticed Donald Knuth said something nontrivial: Theoretically we can compute a very large number of ...

**2**

votes

**0**answers

108 views

### supersingular curve detector

Suppose I give you a prime $p$ and ask for a non-CM supersingular elliptic curve over $\mathbb{F}_p.$ Can this be done in polynomial time (so, polynomial in $\log p$)?

**0**

votes

**1**answer

215 views

### Is unconstrained integer convex optimization problem NP-hard?

Does anyone know a reference to the answer if unconstrained integer convex optimization problem (i.e. $\min_{x\in \mathbb{Z}^N} F(x)$, $F$ is convex and $N$ is NOT fixed) is NP-hard?
Thank you in ...

**7**

votes

**3**answers

238 views

### Can we efficiently compute a third Nash Equilibrium, given two?

A finite, two-player, nondegenerate, symmetric game is defined by a nondegenerate $n \times n$ payoff matrix $A$. If player 1 plays strategy $i$ and player 2 plays strategy $j$, then player 1's ...

**2**

votes

**1**answer

211 views

### Typical dimension of partial derivatives

Let $V$ be the space of all homogenous polynomials over $\mathbb{C}$ in $n$ variables of degree $d$.
Let $l,k$ be two integers and $f\in V$.
Let $\partial^{=k}(f)$ be the space of all partial ...

**2**

votes

**1**answer

224 views

### Complexity of establishing finite groups (non)-isomorphism ?

Question Given two finite groups G and H of the same order N what are the algorithms and what is their complexity (in terms of N) to check is G isomorphic to H or not ? Is there polynomial in N ...

**3**

votes

**1**answer

144 views

### Functions That Can Be Computed Faster Simultaneously Than Expected

The following is an elementary question about circuit complexity. It is different from the kind of thing I have seen discussed, so I would be interested in any work that has been done on this kind of ...

**7**

votes

**2**answers

688 views

### How to compute all irreducible representations of a finite group ? (how GAP is doing this?)

Let us "take" a finite group G. Here "take" I mean any type of group-theoretic description you prefer: e.g. as an explicit subset of GL (or other group) or Cayley table, whatever.
Question: How ...

**2**

votes

**2**answers

247 views

### Lattice reduction on an orthonormal lattice?

Suppose you are given an inner product on a vector space and given a set of linearly independent vectors, and that you have been promised that the lattice they span has an orthonormal basis. Can you ...

**1**

vote

**2**answers

129 views

### Is number of quasi-kernels NP-hard?

A quasi-kernel in a directed graph D is an independent subset of vertices $S$ so that for every $v \in V(D)-S$ either $v->s$ for some $s \in S$ or $v->w->s$ for some $w \in V(D)-S, s \in S$.
...

**0**

votes

**1**answer

93 views

### Provided a list of sets, $L$, computing an array where each entry $q_i \in Q$ is the family of sets in $L$ that have intersection $k$ with $l_i \in L$

I have a set of $(l_1, ..., l_N) \in L$ smaller sets, each with $(r_1, ..., r_M) \in R$ integer elements. I would like create an ordered array of $(q_1, ..., q_N) \in Q$ sets s.t.:
(1) Each $q_i \in ...

**1**

vote

**1**answer

189 views

### Redundancy and Structure of computational problems

It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). ...

**1**

vote

**0**answers

90 views

### Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?

Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?
Equally interesting would be to learn about such problems with a ...

**2**

votes

**1**answer

195 views

### Does Quadratic Programming get easier when it's described by a diagonal matrix?

Generally, Quadratic Programming solves the problem
$$\text{Given }Q, c, A, b,\text{ choose }x \text{ to maximize } x^TQx + c^Tx \text{ subject to } Ax \le b$$
In this form, Quadratic Programming is ...

**2**

votes

**0**answers

171 views

### A natural problem on “cartesian union” of set families (hypergraphs). Does anybody know 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 ...

**2**

votes

**1**answer

111 views

### Any result or conjecture of computaional complexity of formal languange with rational generating function?

As we know that context-free language is in P,any result or conjecture of computaional complexity of formal languange with rational generating function?And more,any result or conjecture of ...

**4**

votes

**0**answers

367 views

### Computational complexity of multiplication in a nilpotent group?

What is the computational complexity of multiplication in a Carnot group ?
Background: A Carnot group is a real nilpotent Lie group $N$ whose Lie algebra $Lie(N)$ admits a direct sum decomposition
...

**22**

votes

**0**answers

534 views

### A combination of two well-known complexity problems

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other ...

**1**

vote

**0**answers

136 views

### Randomized alternative to Buchberger's algorithm

Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra.
Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...

**0**

votes

**1**answer

236 views

### Algorithm for vector space

I have $n$ vectors $e_1 \in (\mathbb Z/2 \mathbb Z)^m,\dots,e_n \in (\mathbb Z/2 \mathbb Z)^m $
and a vector $ v \in (\mathbb Z/2 \mathbb Z)^m $
I need to find the better algorithm which answers ...

**3**

votes

**0**answers

113 views

### Gaussian Elimination in terms of Group Action

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence ...

**3**

votes

**2**answers

1k views

### Generation of All Path in a Directed Acyclic Graph

I am working on a very large dataset of a single DAG whose vertices have a low branching factor. I need to generate all possible (simple) paths starting from the source and write them to a file.
My ...

**12**

votes

**2**answers

437 views

### Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...

**7**

votes

**2**answers

650 views

### Building a Physical Model to Solve Sudoku

Before asking my questions, allow me to begin with a separate example to help clarify what I'm driving at. For terms that are not defined formally, please interpret them as you feel would be most ...