Prev: I Guess it's Obvious I also Like to Write [Mythologies of Reason?]
Next: question about "merging" two context-free languages (CFL)
From: Generic Usenet Account on 13 Aug 2010 01:12
On Aug 11, 7:31 pm, Zahid Faizal <zahidfai...(a)canada.com> wrote:
> The news of Vinay Deolalikar possibly proving that P not-equals NP
> prompted me to again attempt to come up with a layman definition of
> these terms (not the formal definitions, which are confusing and
> circular).  Kindly correct me if I am wrong.

<snip>

>
> Thanks,
> Zahid

I wonder if there are examples of problems that can be solved
efficiently but not verified efficiently.

Thanks,
Gus
From: Tim Little on 13 Aug 2010 05:51
On 2010-08-13, Generic Usenet Account <usenet(a)sta.samsung.com> wrote:
> I wonder if there are examples of problems that can be solved
> efficiently but not verified efficiently.

Sure: "find a Turing machine that halts". Or less impossibly, "find a
graph with a Hamiltonian path".


- Tim
First  |  Prev  | 
Pages: 1 2
Prev: I Guess it's Obvious I also Like to Write [Mythologies of Reason?]
Next: question about "merging" two context-free languages (CFL)