Problem Detail: I’m having a hard time understanding the actual proof of this proposition: $qquad mathsf{NP} subseteq mathsf{P}/log implies mathsf{P} = mathsf{NP}$ The sketch of the proof is on slides 6-8 of this PDF. So I let $L in mathsf{NP}$. That Read More …
Category: Uncategorized
[Solved]: Can we check in polynomial time if the language of a DFA is closed against Kleene star?
Problem Detail: I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it. Read More …
[Solved]: Order a list of whole numbers so that no two numbers have the average of them sitting between them
Problem Detail: Given a whole number N.. Arrange 1 to N in a sequence such that no two numbers have their average sitting between them… Note – If N=20.. average of 19 and 2 = 10.5 is not a whole number Read More …
[Solved]: Proof that ${⟨M⟩ ∣ L(M) mbox{ is context-free} }$ is not (co-)recursively enumerable
Problem Detail: I would like to use your help with the following problem: $L={⟨M⟩ ∣ L(M) mbox{ is context-free} }$. Show that $L notin RE cup CoRE$. I know that to prove $Lnotin RE$, it is enough to find a language Read More …
[Solved]: Is the language of TMs that decide some language Turing-recognizable?
Problem Detail: Is the language $qquad L={ langle text{M} rangle ; | ; text{M is a Turing machine that decides some language} }$ a Turing-recognizable language? I think it’s not, as, even if I am able to tell somehow that a Read More …
[Solved]: Pseudo polynominal time algorithm for Np-Complete Problems
Problem Detail: For problems like knapsack there is pseudopolynominaltime algorithm and it is np-complete. So we reduce every other problem in np in polytime to knapsack. But why don’t we have then a pseudopolynominaltime algorithm for all problems in np? Asked Read More …
[Solved]: Can a transcendental number like $e$ or $pi$ be compressed as not algorithmically random?
Problem Detail: The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An algorithmically random number is a number (in some encoding, usually binary) for which the shortest program Read More …
[Solved]: Relation between the “Point-Cover-Interval” problem and the “Interval Scheduling” problem
Problem Detail: Point-Cover-Interval Problem: Given a set $mathcal{I}$ of $n$ intervals $[s_1, f_1], ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains some point, that is $forall I in mathcal{I}: Read More …
[Solved]: Showing that a problem in X is not X-Complete
Problem Detail: The Existential Theory of the Reals is in PSPACE, but I don’t know whether it is PSPACE-Complete. If I believe that it is not the case, how could I prove it? More generally, given a problem in some complexity Read More …
[Solved]: What is the asymptotic runtime of the best known TSP solving algorithm?
Problem Detail: I always thought that TSP currently requires time exponential in the number of cities to solve. How, then, has Concorde optimally solved a TSP instance with 85,900 cities?!? Is this a typo? Is the base of the exponential 1.0000000000000001 Read More …
