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.

Filter by
Sorted by
Tagged with
1
vote
1answer
252 views

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-...
0
votes
0answers
23 views

semiparametric index model with heteroskedasticity

I'm trying to estimate a semiparametric binary response model with index heteroscedasticity in R. That is, I have a model defined with $y_i = \mathbf{1}\{\beta_0 + \beta_1 x_{1i} + \beta_2 x_{2i} + \...
1
vote
0answers
320 views

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 ...
13
votes
3answers
2k views

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 ...
12
votes
1answer
271 views

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$ ...
1
vote
0answers
74 views

Parameters of energy function for TSP [closed]

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