I’ve been wondering if there are known solutions for algorithm of creating a school timetable. Basically, it’s about optimizing “hour-dispersion” (both in teachers and classes case) for given class-subject-teacher associations. We can assume that we have sets of classes, lesson subjects and teachers associated with each other at the input and that timetable should fit … Read more
What are the differences between NP, NP-Complete and NP-Hard? I am aware of many resources all over the web. I’d like to read your explanations, and the reason is they might be different from what’s out there, or there is something that I’m not aware of. Answer I assume that you are looking for intuitive … Read more
Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles? Answer AttributionSource : Link , Question Author : Thinh D. Nguyen , Answer Author : Community
Given a set of strictly positive numbers a1,…,an, the problem is to determine if ⌊n/2⌋ different indexes i1,…,i⌊n/2⌋ exist so that aijaij−1=aij+1aij for 2≤j≤⌊n/2⌋. How to show that this problem is in co-NP ? Answer P is a subset both of NP and of co-NP. Do you think the problem is in P? (O(n^3) solution … Read more
A friend and I have tried for several hours to try and find a reduction from independent set to longest path, but the results have not been fruitful. We have tried many methods of graphing and complementing but are well and truly lost. Any help would be much appreciated! Answer AttributionSource : Link , Question … Read more
How can i show/explain/prove that Max-Cut is in NP? “For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem.” Thanks! Answer The decision version of MAX-CUT is as follows: … Read more
Suppose in a plane, there is a set of points, whose distance to (0,0) is always 1: [(0,1),(1,0),(0.707,0.707),(0.707,−0.707),…] Each point is assigned with a weight (possible negative): [w(0,1)=1,w(1,0)=2,w(0.707,0.707)=−1,w(0.707,−0.707)=−2,…] Suppose the standard deviation of the points are defined as the top answer here: https://stats.stackexchange.com/questions/13272/2d-analog-of-standard-deviation Find a subset of points S such that SUM(w)×STD is maximized. My … Read more
This question follows Unique 3SAT to Unique 1-in-3SAT Consider an AND gate such that (A ∧ B) = C. It can be trivially expressed in 3SAT with 4 clauses and no extra variables. (A∨B∨¯C)∧(A∨¯B∨¯C)∧(¯A∨B∨¯C)∧(¯A∨¯B∨C) | A | B | C | |—|—|—| | 0 | 0 | 0 | | 0 | 0 | 1 … Read more
Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete. Is it possible to show directly that Subset Sum ≤p 3-Partition, or would I have to do Subset Sum ≤p Partition ≤p 3-Partition? … Read more
Complexity class IP includes all problems that can be solved using an interactive proof system where the verifier is a probabilistic polynomial time machine, and the prover is a machine of an unbounded power. It is known to be equal to PSPACE. Making the verifier a deterministic machine would make a complexity class dIP which … Read more
