127 views

### determine Eulerian or Hamiltonian

I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions. For eulerian, I can say that the graph has ...
135 views

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \... 2answers 109 views ### Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers) Let me explain my trouble by another example. The wiki page says that Lattice problems are an example of NP-hard problems However, by clicking NP-hard, i find this definition A decision problem H ... 0answers 20 views ### Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same? I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ... 2answers 50 views ### Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following: There exists a believed-today NP-hard problem ... 1answer 79 views ### Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well? This relates to an answer for this question. The opinion said that: Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most ... 0answers 25 views ### are all problems in P in NP [duplicate] I know this is a similar question to this post, but I want to further clarify my understanding. In the picture from wikipedia: I understand that every problem that's in$P$is also in NP. does this ... 3answers 255 views ### Why don't passwords prove P != NP? Pardon my ignorance on the matter but, Verifying passwords = Polynomial (linear) Guessing passwords = Exponential Since each guess has nothing to do with one another, exponential time is best possible ... 2answers 356 views ### P vs NP and Angle Trisection (serious question) I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level. My understanding from many popular-level sources (like Scott ... 2answers 96 views ### Is P contained in NP-hard? I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me. NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained ... 1answer 70 views ### Reframing decision, counting, enumeration, and search as optimization The top accepted answers to the questions below allude to two complexity classes of optimization problems: NPO and PO (in relation to NP and P for decision problems): Decision problems vs "real" ... 0answers 63 views ### Is$k$-Clique NP-hard? [duplicate] On my lecture note it was written that "Finding a clique of size$k$in a graph is NP". Later in an example for reduction the following was written: "Assume we know how to answer "Is there a clique ... 1answer 144 views ### Are problems in NP$\cap$coNP less difficult than those in NP-complete? I am taking a complexity class now, and I struggle to understand the concept of "hardness": Assume that$L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption$\mathsf{NP} \neq \...
I've seen in many textbooks if say we have a problem $Q$, we write a non-deterministic algorithm in polynomial time to solve problem $Q$, and then from that point it results that $Q\in NP$. Why is ...