JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Question about NP | Reply
"There is one tricky special case you sometimes need to be aware of. To write a (possibly large) number we need only logarithmic space. (E.g. to write 123456, we need only roughly log10(123456) digits.) This is why the naive primality test does not run in polynomial time - its runtime is polynomial in the size of the number, but not in its number of digits! If you didn't understand the part about polynomial time, don't worry, we'll get there later."

I am not sure about something.
If I want to prove P=NP and I make an algorithm to solve some NP-Complete problem in polynomial time where the problem takes an input number N. What's the input size? N? or log(N)?
I don't understand when do I have to use as input size the number of bits and when to use just the number represented.
Can anyone suggest any free book to read more about this?
Thanks in advance.
Re: Question about NP (response to post by midrux) | Reply
As a general rule, the algorithm should be polynomial in the size of the input (in bytes, for example). A general tree with N vertices needs O(N) bytes to be represented, for example, so it should be polynomial in N, but a number takes O(log N) bytes to be represented, so the algorithm should be a polynomial in log N.
Re: Question about NP (response to post by MauricioC) | Reply
Thanks!
But if a number needs O(log N) bytes to be represented then why a tree with N vertices needs O(N) and not O(N log N)... I mean, (log N) for each vertex.
And how do you know that the representation you are using is not exponencially bigger than another representation (that maybe no one knows until now)?
I mean, suppose someone wants to prove that P = NP and suppose he solves an NP-Complete problem (related with graphs) in polynomial time using as input size the size of a standard representation of a graph.
Is it necessary that he also proves that there is no way of represents a graph with an input size exponencially smaller? (Maybe using http://en.wikipedia.org/wiki/Entropy_%28information_theory%29 ?).
Ok... so many questions from me...
Does someone knows a good book?
Thanks again
Re: Question about NP (response to post by midrux) | Reply
Yes, a (labeled) tree on n vertices can be represented with O(n log n) bits, and this is optimal by Cayley's formula:
  • http://en.wikipedia.org/wiki/Cayley%27s_formula

  • So you're right in pointing out you need more than n bits overall. (But notice that any bound that is polynomial in n log n, or in n^10 for that matter, is also polynomial in n).

    No, it is not necessary (nor does it make much sense) in order to prove that a certain problem is NP-complete to show that there is no smaller representation. Input representation is in fact part of the problem definition. A problem can become significantly easier or harder if instances are encoded in a different way. For a trivial example, notice that if your instances to SAT are formulas padded with 2^n garbage bits, then you obviously can solve this "variant" of SAT in polynomial time.

    The reason why this is often glossed over is that usually all "reasonable" representations are polynomially related in size (and moreover you can turn one into another in polynomial time), and it doesn't matter which one you use as long as you don't try to "cheat"
    (e.g. by including in the encoding data that is hard to compute from the original representation, or making it significantly longer).

    As for good books, the best one on complexity is in my opinion Arora and Barak's book, you can find a draft online at
  • http://www.cs.princeton.edu/theory/complexity/

  • I'm not sure if it is the most suitable for beginners (it covers a huge amount of material), but you may be interested in having a look at the first few chapters.
    Re: Question about NP (response to post by elhipercubo) | Reply
    Thank you so much!
    "Input representation is in fact part of the problem definition"
    I was missing that... that's the point.

    "The reason why this is often glossed over is that usually all "reasonable" representations are polynomially related in size (and moreover you can turn one into another in polynomial time), and it doesn't matter which one you use as long as you don't try to "cheat""

    I knew that but then I read (from http://en.wikipedia.org/wiki/Context_of_computational_complexity):
    "In the other direction, succinct circuits are compact representations of a limited class of graphs that occupy exponentially less space than ordinary representations like adjacency lists."

    And that brings me some doubts about it.
    I would try with that book!
    Thanks again!
    RSS