Statistical Analysis Stack Exchange
Statistical Analysis Stack Exchange

Questions tagged [np]

NP stands for nondeterministic polynomial time. One characterization: the set of decision problems solved by a nondeterministic Turing machine in polynomial time.

It is the complexity-class of decision problems solved by a nondeterministic Turing machine in polynomial time. It is equivalently the set of problems whose solution is verifiable in polynomial time by a deterministic Turing machine.

Reference: http://en.wikipedia.org/wiki/NP_%28complexity%29

6 questions
14
votes
3 answers

Formula for dropping dice (non-brute force)

First of all I'm not sure where this question should be posted. I'm asking if a statistics problem is NP-Complete and if not to solve it programmatically. I'm posting it here because the statistics problem is the center point. I'm trying to find a…
SkySpiral7
  • 253
  • 2
  • 8
13
votes
1 answer

Testing certain contrasts: Is this provably a hard problem, or not?

I posted this to mathoverflow and no one's answering: Scheffé's method for identifying statistically significant contrasts is widely known. A contrast among the means $\mu_i$, $i=1,\ldots,r$ of $r$ populations is a linear combination $\sum_{i=1}^r…
Michael Hardy
  • 7,094
  • 1
  • 20
  • 38
1
vote
0 answers

Parameters of energy function for TSP

I am reading this paper by Hopfield et al. On page six, the authors defined the energy function of the Traveling-Salesman-Problem (TSP) mapped onto an artificial neural network as follows: $$E = \frac{A}{2} \sum_X \sum_i \sum_{j \ne i} V_{Xi} V_{Xj}…
Omar Shehab
  • 179
  • 1
  • 10
1
vote
0 answers

Is there a general theorem about NP-hardness of training neural networks?

It is often stated that training a neural network is "well-known" to be NP-hard. Looking through the literature the often quoted papers are 1 and [2]. [1] proves the NP-hardness for finding an exact match, i.e. finding a hypothesis $h$ with $\forall…
olukatorzu
  • 11
  • 1
1
vote
1 answer

What does it mean for K mean problem to be NP hard and why?

Given a decision problem (a problem with yes or no answer), the problem is said to be NP-hard if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time. Recall that NP-complete represents the set of all problems X in NP…
The man of your dream
  • 171
  • 8
1
vote
0 answers

Why is Max Likelihood Estimation NP-Hard in General

I am watching the lecture here and the author says that in the machine learning setting where data is assumed to be generated by a model with a few parameters: Max Likelihood parameters are NP hard to find in general (non convex objective). And in…
Rafael
  • 1,109
  • 1
  • 13
  • 30