Problem Detail: HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ halts on input $w$ The complement of HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ doesn’t halt on input $w$ Show that Read More …
Blog
[Solved]: Undergraduate Computer Science Textbooks
Problem Detail: What books would you recommend for someone starting B.Sc in Computer Science? My Personal Info: I am currently looking at B.Sc in Computer Science (Games), which is computer science, accept for the last year which is tailored more towards Read More …
[Solved]: Is there any study or theory behind combining binary search and interpolation search?
Problem Detail: I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files by date/time window. Read More …
[Solved]: Are there established complexity classes with real numbers?
Problem Detail: A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P’$ that is known to be NP-complete to my problem $P$ (with a poly-time many-one Read More …
[Solved]: Job scheduling with a bottleneck problem
Problem Detail: Given $n$ jobs $J_1,J_2,…,J_n$, each job requires $T_i > 0, T_i in N$ time to complete. Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a time and both Read More …
[Solved]: What algorithms exist for solving natural number linear systems?
Problem Detail: I’m looking at the following problem: Given $n$-dimensional vectors of natural numbers $v_1, ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$’s with natural number coefficients? i.e. are there some $t_1, ldots, t_m Read More …
[Solved]: Making feature vector from Gabor filters for classification
Problem Detail: My aim is to classify types of cars (Sedans,SUV,Hatchbacks) and earlier I was using corner features for classification but it didn’t work out very well so now I am trying Gabor features. code from here Now the features are Read More …
[Solved]: What is wrong with this seeming contradiction with a paper about AND-compression of SAT?
Problem Detail: Got a simple construction seemingly contradicting a paper assuming plausible conjecture. Since it is unlikely the conjecture to be false, what is wrong with the argument? From a paper An AND-compression is a deterministic polynomial-time algorithm that maps a Read More …
[Solved]: Partition partition with constraint of equal size
Problem Detail: I see the problem here which is the well know partition problem but with constraint that the size of both sets must be equal. I look at the answer and I don’t understand that why Colin said add max(S)⋅length(S), Read More …
[Solved]: Showing that the set of TMs which visit the starting state twice on the empty input is undecidable
Problem Detail: I’m trying to prove that $L_1={langle Mrangle mid M text{ is a Turing machine and visits } q_0 text{ at least twice on } varepsilon} notin R$. I’m not sure whether to reduce the halting problem to it or Read More …
