dspyz
• Member for 8 years, 11 months
• Last seen this week

Ok, I got it. The answer is no. This can be solved in poly-time. For each 3-or-more-term clause, select a literal and set it to be true. Then solve the remaining 2-sat problem. If any one ...

S(C(KM)M)I ~ MM suffices The reduction is as follows: S(C(KM)M)Ix C(KM)Mx(Ix) C(KM)Mxx KMxMx MMx

This problem is NP-hard. As proof, the maximal clique problem (or rather the decision variant find-a-K-clique) can be reduced to this problem as follows. Start with a problem on a graph with N ...

Finding the prime factors of n by trial division when the list of primes is already given. There are $\theta(\frac{n}{\log(n)})$ primes less than n so if these primes are given to you, then trial ...

I wrote a short clingo program to check the small values (it can quickly handle graphs of up to 7 vertices. Beyond that, the grounding can take quite a while): I got this table ...

Ok, I have an algorithm I believe is O(nlog*(n)), that's n log-star(n) (log-star n is constant for all practical purposes), but it's hard to prove and I suppose I could be wrong. The running time ...