**1**

vote

**0**answers

129 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

227 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

363 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

107 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

248 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

418 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

320 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

252 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

99 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

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

**8**

votes

**3**answers

816 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

109 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

232 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

251 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

233 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

145 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

761 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

257 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

132 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

193 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

211 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

178 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

113 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

411 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

552 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

138 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

237 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

117 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

506 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

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

**10**

votes

**1**answer

691 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

**1**answer

264 views

### What is the largest tensor rank on matrix.

A tensor rank of tree dimentional matrix $M[i,j,k], i,j,k\in [1,\ldots,n]$ is a minimal number of vectors $x_i,y_i,z_i$, such that $M=\sum_{i=1}^d x_i\otimes y_i\otimes z_i$.
From dimension argument ...

**3**

votes

**2**answers

165 views

### Determination of rationality and computing a rational parametrization

Suppose I have a hypersurface in $\mathbb{C}P^n$ given by some $f(z_1, \dots, z_{n+1}) = 0.$ Is there an algorithm which returns a rational parametrization if there is one, and "not rational" ...

**4**

votes

**2**answers

328 views

### Sets of vectors related by a rotation

We have a two sets of vectors ($\mathbb{C}^d$), $A=\{ v_1, \ldots v_n\}$ and $B=\{u_1, \ldots u_n\}$.
The question is if there is an efficient solution (polynomial in $n$) for checking whether $A$ ...

**18**

votes

**1**answer

2k views

### How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.8})$ for the multiplication of two $n \times n$ matrices. However, the constant is so large that ...

**0**

votes

**1**answer

190 views

### graph to tree and graph isomorphism problem

Sorry if the following are stupid questions (i do not know much about the graph theory).
1. Motivation
we do not know the graph isomorphism problem in class P or NP complete and it is P in the ...

**3**

votes

**1**answer

714 views

### Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i).
I guess complexity of its volume calculate is higher than linear in "N", am I right ?
(Is the complexity ...

**13**

votes

**1**answer

637 views

### Forcing over set theory versus forcing over arithmetic

I've been trying to understand better some of the research on forcing over bounded arithmetic and its connections with lower bounds in complexity theory. For example, Takeuti and Yasumoto have some ...

**2**

votes

**1**answer

349 views

### Oracle Results: P^A = NP^A

Context
In the work of Baker, Gill, Solovay, we know that there exists some oracle A s.t.
$$P^A = NP^A$$.
Now, in CCAMA, this oracle $A$ is given as an EXP complete language.
Question:
Can we do ...

**1**

vote

**0**answers

76 views

### Deciding / Approximating Parity of Small Depth Decision Trees

Let C be a circuit such that:
C: $\{0,1\}^n$ to $\{0,1\}$
the top most gate is a parity gate
all the inputs to the parity gate are small depth decision trees
there is a total of $2^{ log^k n}$ ...

**5**

votes

**2**answers

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

**1**

vote

**3**answers

2k views

### How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}
Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.
Example:
Input ...

**2**

votes

**3**answers

277 views

### Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it.
My question is as follows.
Given a positive integer $k$, determine a set of properties ...

**4**

votes

**2**answers

288 views

### Computational complexity of Knot polynomials

What's known about computational complexity of different types of knot invariant polynomials?
For example, Evaluating Jones Polynomial is known to be #P hard.
Is there any reference that surveys such ...