dspyz
  • Member for 8 years, 11 months
  • Last seen more than a week ago
Is Almost-2-SAT NP-hard?
8 votes

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

View answer
Can a normal form term be extensionally equivalent to a term with no WHNF?
Accepted answer
3 votes

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

View answer
M-clique covers in complete graphs
Accepted answer
2 votes

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

View answer
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
2 votes

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

View answer
Number of cycles in a Graph
1 votes

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

View answer
Linear-time algorithm for getting ends of diametral paths in special sequence of trees
1 votes

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

View answer
Transitive feedback arc set (TFAS): NP-complete?
1 votes

I ran a short clingo program which reported no graph without a TFAS, but there was a bug. I fixed it and now it verifies there's no graph without a TFAS for n=8 or less. For n=9, it finds this one: ...

View answer
Assign each biclique to a distinct left
0 votes

Thanks to Tsuyoshi's comment, I have the solution. It's always possible to take some subset of lefts (of size k) and construct a set of k bicliques covering all the edges connected to those lefts (...

View answer