daniel pehoushek's user avatar
daniel pehoushek's user avatar
daniel pehoushek's user avatar
daniel pehoushek
  • Member for 11 years, 9 months
  • Last seen more than 2 years ago

(gre scores 800M 800V 780A, and proud of them)

Recently, I have a curiously short proof that NP=#P.
1. Correct programs for solving NP imply that every satisfiable solution is a valid answer.
2. NP!=#P implies NOT all solutions are valid answers.
3. Therefore NP=#P.

I also have a program available that solves #sat, recently counting nearly half a quadrillion solutions to a 4cnf 4 coloring problem on a 6th degree graph, in eleven weeks.

The first sublinear string matching algorithm, for the average case, was invented by me as far as I know. Commercially available in 1985, GMACS, GCLISP, from Gold Hill Computers. Finally published at CPM98, with two frenchmen. China uses it to filter emails. Some americans maybe can use it to connect the dots... Also may be good basis for hunting virusses in networks faster than they may be able to spread.

I also designed some pentium register sets and cache memory circuits for hardware emulation, at Quickturn Design Systems, in the early nineties. Intel was our main customer.

I wrote an NlogN vison system for Cardiff Software, in the mid nineties. The "PLUS" vision system partitions images into four parts, then does vision on each of the four parts, and links up results in linear time. The key was a vector that grew with a fibonacci ratio.

I wrote Stanford Qlisp (parallel lisp) in the late eighties. The key parts for load balancing were the log high local task stacks, and the idle cycle that used one word of memory to begin at successor location of last. Locally LIFO globally FIFO. Good for many types of real resource allocation, including gasoline and number supplies at banks, with very low overhead.

The Cardinal Equivalence Theorem and followups are the area that I have worked on for the last decade.

This user doesn’t have any gold badges yet.
This user doesn’t have any silver badges yet.
bronze badges

This user hasn’t posted yet.