Subject: RE: [hackers-il] RE: Re: Concrete and Abstract Stuff (was: Re: Re : Re : Prerequisite learning?)

From: Chen Shapira <[email-masked]>
Date: Mon, 4 Mar 2002 14:29:24 +0200

> -----Original Message-----
> From: Shlomi Fish [mailto:[email-masked]]
> Sent: Monday, March 04, 2002 2:16 PM
> To: [email-masked]'
> Subject: [hackers-il] RE: Re: Concrete and Abstract Stuff 
> (was: Re: Re:
> Re : Prerequisite learning?)
> 
> 
> On Mon, 4 Mar 2002, Chen Shapira wrote:
> 
> >
 
> But something that takes exactly 10 machine instructions takes O(1),
> rather than O(10). Using an array of pointers to structs has the same
> complexity as using an array of structuts. However, sorting 
> the former is
> a relatively small O(n*log(n)) while sorting the large is much slower.

Of course.
What he ment was that you can't assume a basic operation that sorts and then
say that sorting is O(1).
So we need to define what is a basic operation. Which means that we must
define a machine language for our abstract computer.
 
> Complexity (O's, Thetas and their ilk) is nice, but it's not 
> the only way
> to evaluate an algorithm. I was told that in some forms of Real-Time
> programming people had to count the number of clock ticks it 
> would take to
> execute every code.

Of course, but it seems like basic algorithm books (i.e. Cormen or Hopcroft)
ignore the fact most of the time. And remember it again when they explain
how insertion sort is better than selection sort.

> So, yes, knowledge of Assembler (or machine language) helps in
> understanding. However, only experience can help you become a good
> programmer with a much better understanding of how algorithms and code
> works.

Sure. But he wasn't trying to create better programmers, he was trying to
write a formal algorithms reference. (Note that he only proved them and
analyzed asymptotic complexity, he doesn't tell which one to use)

But he does occasionaly remembers that real problems exist. for example he
claims that for very small arrays, bubble sort is the quickest, so one
sorting algorithm uses qsort to partition into parts with 9 elements each,
and then uses bubble-sort to sort each part.

> Then there are faux-amies. You would not put 20! permutations in a C
> array, would you? But in haskell defining a lazy list of them is quite
> common, and will not blow out memory.
> Lazy eval can make some very nice tricks possible. Without good
> understanding of it one will write Haskell code which is much less
> elegant.

Lazy lists sound very very cool. 
Does it has anything to do with the use of assembly for complexity analisys?
I was mostly talking time complexity, and not memory complexity.

It is very very difficult to compute memory complexity of an algorithm, even
in assembly.
There's caching to take into account...

Thanks,
Chen.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 04 Mar 2002 17:47:05 +0200

Chen Shapira <[email-masked]> writes:

> ignore the fact most of the time. 

This misses the point. Cormen et al and other algorithms books are not
concerned with how long a particular O(1) operation takes on a
specific platform (which might be very important for a real-time
programmer trying to create a product by a spec that places severe
performance restrictions, but is quite irrelevant for study of
algorithms). The O notation and other complexity analysis techniques
deal with scalability questions, i.e. if my input is twice as long
will I need twice as nuch time, 4 times as much time, etc? This is
what is often important in, say, generic sorting algorithms, and that
is why O(n*log(n)) is considered such an improvement over O(n^2) in
many cases. Do the arithmetic to see the effect (you can make
different assumptions regarding the cost of O(1) in clock ticks), or
consult your old lecture notes.

One common mistake regarding complexity analysis on the other (in
relation to O(1), and in relation to theory vs. practice(*)) extreme
is dismissing NP and NP-complete algorithms outright, which quite a
few people are prone to. NP does not mean "not feasible". Tell me what
the size of your problem is first...

(*) In theory, there is no difference between theory and practice.

-- 
Oleg Goldshmidt | [email-masked] 
Only wimps use tape backup: real men just upload their important 
stuff on ftp, and let the rest of the world mirror it. [L. Torvalds]

---

From: "Nadav Har'El" <[email-masked]>
Date: Tue, 5 Mar 2002 17:50:37 +0200

On Mon, Mar 04, 2002, Oleg Goldshmidt wrote about "Re: [hackers-il] RE: Re: Concrete and Abstract Stuff (was: Re: Re?: Re : Prerequisite learning?)":
>...

You're right that if you assume that your computer is compatible with a
turing machine, i.e., there exists a constant C where each step you do
in a turing machine you can do in up to C steps on your computer (and
vice versa), then the actual details of the assembly language don't matter
at all for O(...) calculations.
It doesn't matter if addition of 32 bits takes 17 clock cycles and
multiplication of 16 bits take 72 clock cycles - as long as all these things
are bounded by one constant.

On the other hand, if you imagine a weird computer with a "magical" assembly
language that can, say, sort an array of any size in one clock cycle (such a
magical assembly instruction is usually called an "oracle"), then obviously
all your O(...) calculations are going to end up different.

The course Technion course "complexity theory" talks quite a bit (among a lot
of other things) about what you can achieve (and what you cannot acheive) by
adding oracles to a turing machine (e.g., oracles with NP power, oracles
with oracles with NP power, and ad inifinitum). It's an interesting, but very
abstract and quite difficult, course.

-- 
Nadav Har'El                        |        Tuesday, Mar 5 2002, 21 Adar 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Cement mixer collided with a prison van.
http://nadav.harel.org.il           |Look out for sixteen hardened criminals.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 06 Mar 2002 09:13:24 -0500

"Nadav Har'El" <[email-masked]> writes:

> You're right that if you assume that your computer is compatible
> with a turing machine,

Are there computers - today - that are not Turing machines? Are the
latest 5-7 qubit quantum computers not Turing machines?

> On the other hand, if you imagine a weird computer with a "magical"
> assembly language that can, say, sort an array of any size in one
> clock cycle (such a magical assembly instruction is usually called
> an "oracle"), then obviously all your O(...) calculations are going
> to end up different.

No, just those involving sorting. Complexity analysis of finding a
shortest path on a graph will presumably remain valid until someone
implements a Dijkstra Oracle (tm) for this architecture. And when
all the useful algorithms are exhausted in this way humanity will be
free to analyze complex combinations of sortings, searches, etc. My
guess is that modern complexity analysis will be applicable and
relevant to that task.

> The course Technion course "complexity theory" talks quite a bit
> (among a lot of other things) about what you can achieve (and what
> you cannot acheive) by adding oracles to a turing machine (e.g.,
> oracles with NP power, oracles with oracles with NP power, and ad
> inifinitum). It's an interesting, but very abstract and quite
> difficult, course.

Since I never took such a course, I am curious: is there a Universal
NP-complete Oracle?

-- 
Oleg Goldshmidt | [email-masked] 
If it aint't broken it hasn't got enough features yet.

---

From: Omer Zak <[email-masked]>
Date: Wed, 6 Mar 2002 09:10:32 +0200 (IST)

> "Nadav Har'El" <[email-masked]> writes:
[... snipped ...]
> Since I never took such a course, I am curious: is there a Universal

Tsk, tsk!  Are you asking if there is a God?
                                             --- Omer
There is no IGLU Cabal.  History records series of bloody and messy 
religious wars at sites of attempts to start IGLU Cabals.
WARNING TO SPAMMERS:  see at http://www.zak.co.il/spamwarning.html

---

From: Oleg Goldshmidt <[email-masked]>
Date: 06 Mar 2002 10:25:23 +0200

> Tsk, tsk!  Are you asking if there is a God?

No. I am asking if there is an Oracle. Note that it is not equivalent
to asking if there is a Larry Ellison. ;-)

All NP-complete problems are equivalent, so I am asking whether there
is a (gedanken) Oracle that can solve all of them. One way to
construct such an oracle is to build an oracle to solve one
NP-complete problem, e.g. finding Hamiltonian circuits, in O(1), and
an algorithm to morph all other NP-complete problems into that one.
An interesting question is, can we do the morphing in O(1)?

Well, it's all (partly) tongue-in-cheek...

---

From: "Nadav Har'El" <[email-masked]>
Date: Wed, 6 Mar 2002 13:31:27 +0200

> latest 5-7 qubit quantum computers not Turing machines?

Of course they aren't, that's their whole point!

There are certain things that you can't do on a deterministic turing machine
in polynomial time, but can do in polynomial time on a quantum computer. Of
course the difference between polynomial and exponential is rather silly
when N=5, but I'm talking about the theory.

There are other people on this list who are more qualified than me to talk
about quantum computation...

> guess is that modern complexity analysis will be applicable and

I meant what I said. Sorting isn't a very interesting algorithm (since it's
still in P, with a very low complexity O(nlogn)), but when you have an
oracle for a certain algorithm you might implement other algorithms using
that one and perform faster. It is conceivable that with a O(1) sorting
algorithm, many other (but not all!) O(nlogn) algorithms may be done in
O(1), some O(n^7) algorithm can be done in O(n^6), and so on. If your
oracle is not in P (e.g., it is NP-complete and you assume P!=NP) than
this immediatly gives you a huge amount of power you didn't have in P.

> Since I never took such a course, I am curious: is there a Universal

The whole concept of NP completeness implies that all NP-complete algorithms
are equivalent, i.e., the input to one can be transformed to input to another
in polynomial time. So yes, if you have one NP-complete Oracle (e.g., SAT)
your computer can do *any* other NP-complete things in polynomial (but not
constant!) time.

I don't have time right now to explain this in more detail. If I got something
wrong, please correct me (I'm not really a complexity-theory expert).

-- 
Nadav Har'El                        |      Wednesday, Mar 6 2002, 22 Adar 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |The message above is just this
http://nadav.harel.org.il           |signature's way of propagating itself.

---

From: Oleg Goldshmidt <[email-masked]>
Date: 06 Mar 2002 14:01:56 +0200

> Of course they aren't, that's their whole point!

Well, I am not so sure about "of course", I still have not made up my
mind regarding whether or not it is some massive parallelization
technique (the machine crunching various components of a mixed quantum
state in parallel).

> There are other people on this list who are more qualified than me
> to talk about quantum computation...

Being a physicist by education, I am not really one of them. I do need
to read up on it (and I am just a sequential apparatus with a
relatively complicated scheduler, so it takes time). Another thing I
never understood was how the result would be obtained from a quantum
computer without collapsing the system's wavefunction (on an intuitive
level, this looks like defeating the purpose: saying that the result
is somewhere in the complex superposition of states and actually
getting to it are two different things). I must be missing a few basic
things in the whole picture, since (intensely practical) minds like
Feynman would certainly have caught basic flaws in the argumentation
early on. So it's back to the literature for me. As soon as I find
this very last bug in the program, that is... ;-)

> It is conceivable that with a O(1) sorting algorithm, many other
> (but not all!) O(nlogn) algorithms may be done in O(1), some O(n^7)
> algorithm can be done in O(n^6), and so on.

Sure, but this is exactly what I said. There is little utility in
memorizing the actual order of different algorithms - it's their
relative scaling that is important. These oracles don't invalidate the
complexity analysis. You can arbitrarily assign O(1) cost to sorting
(or any other) algorithm that is a basic block of your calculation,
and continue with [theoretical] complexity analysis as usual.

> The whole concept of NP completeness implies that all NP-complete
> algorithms are equivalent, i.e., the input to one can be transformed
> to input to another in polynomial time. So yes, if you have one
> NP-complete Oracle (e.g., SAT) your computer can do *any* other
> NP-complete things in polynomial (but not constant!) time.

That's what I guessed, but it was just a guess. Now I can refer to an
expert opinion! Yes, you did say you were not an expert, but the above
sounds intuitively obvious[*] to me.

[*] I have a definition of "intuitively obvious" (as opposed to
    "obvious") in mind, but that's another thread ;-)

---

From: Omer Zak <[email-masked]>
Date: Wed, 6 Mar 2002 11:01:35 +0200 (IST)

> to asking if there is a Larry Ellison. ;-)

The point that this particular oracle (the NP-complete oracle) is
equivalent to the way God is described in monotheistic religions (God who
knows all and is present everywhere).

> An interesting question is, can we do the morphing in O(1)?

More probably in O(N) time.  But even O(N^100) would be very good deal.

                                             --- Omer
There is no IGLU Cabal.  The problem of founding an IGLU Cabal has been
proven, in a surprise move, to be equivalent to the question of existence
of God, fully-tolerant religions and NP-complete oracles.
WARNING TO SPAMMERS:  see at http://www.zak.co.il/spamwarning.html

---

From: "Nadav Har'El" <[email-masked]>
Date: Thu, 7 Mar 2002 13:35:25 +0200

> knows all and is present everywhere).

Actually, NP languages are not in any sense the class of most complicated
problems imaginable, so being able to solve them doesn't make you God :)

Some people somehow got the impression that "NP" means "non-polynomial",
but of course it doesn't: NP means "non-deterministic polynomial" - the class
of languages that can be recognized by a non-determinstic turing machine
(which has a very specific and not very intuitive definition).

There are bigger (actually nobody knows if they're really bigger, but at least
they are not smaller) classes like PSPACE, the class of languages that can
be recognized by a deterministic turing machine with polynomial memory
requirements (and no bound on the computation time).

So an NP-complete oracle is not omnipotent. If P!=NP (nobody has proven this
yet... It's the biggest open problem in this area), Adding an NP-complete
oracle to P gets you one step closer to PSPACE. Adding an oracle of this new
type to NP gets you another step, and so on. This is known as the "polynomial
hierarchy". If I remember correctly, nobody yet knows if the polynomial
hierarchy ends in PSPACE, whether it gets to PSPACE in 1 step, 7 steps, or
an infinite amount of steps. Complexity theory is filled with open questions...

> More probably in O(N) time.  But even O(N^100) would be very good deal.

Actually, I don't think that you can do better than saying "polynomial
time", with possibly a different exponent for different NP languages.

P.S. As usual, please correct me if I've made some embarassing mistakes
in the theory...

-- 
Nadav Har'El                        |       Thursday, Mar 7 2002, 23 Adar 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |I want to be a human being, not a human
http://nadav.harel.org.il           |doing -- Scatman John

---

From: Dan Kenigsberg <[email-masked]>
Date: Mon, 11 Mar 2002 14:50:21 +0200 (IST)

Ten years ago, on March 1992, I had a little bet with my father.

He said that in ten years there will be an automatic translation from hebrew to
english. I said there will not be.

We agreed that a real automatic translator should accept a random entry from the
Hebrew Encyclopedia, and translate it into a readable english text.

Would you please help us decide who has won that bet?

Dan.

---

From: Shlomi Fish <[email-masked]>
Date: Mon, 11 Mar 2002 19:21:32 +0200 (IST)

> Would you please help us decide who has won that bet?

It depends: there are relatively good translators out there. Not
necessarily from Hebrew to English, but nonetheless. However, most of them
can become confused or tricked by extermely complicated or highly
technical text, and will not produce the correct results.

I don't think there exists an automatic translator that will take any
random entry from the Hebrew Encyclopedia and translate it perfectly to
English. If someone can enlighten me about a really good translator,
please do.

Regards,

	Shlomi Fish

> Dan.
>
>
>
> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 11 Mar 2002 19:31:30 +0200

> Hebrew Encyclopedia, and translate it into a readable english text.

Dan, I seem to remember a few years ago you and I went to a computer trade-
show, and we saw one company selling a Hebrew-English translation software.
I remember it was "sort-of working", but was certainly not perfect. I think
that similarly to the babelfish.altavista.com software, it would generate a
translation that would be readable, but make you laugh at times [1] and be
quite inaccurate at others.

I'd bet that automatic translation will not reach perfect quality (i.e., the
quality of a professional human translator) in less than 30 years... :)

[1] Once I translated a German email I got into English. It insisted in
    translating the word "email" (that was used in that German text, to talk
    about electronic mail) into "enamel" :)

-- 
Nadav Har'El                        |        Monday, Mar 11 2002, 28 Adar 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |Attention: There will be a rain dance
http://nadav.harel.org.il           |Friday night, weather permitting.