Prev: [Port%d] \\.\HCD%d
Next: On The Question of Absolute Undecidability
From: Anonymous Number of People on 25 Oct 2009 18:50
On Oct 22, 4:48 am, "H. J. Sander Bruggink" <brugg...(a)uni-due.de>
wrote:
> On 10/22/2009 01:32 AM, Tegiri Nenashi wrote:
>
> > Factorization problem is not hard in unary system. Any other NP-
> > complete problem that doesn't depend on number encoding?
>
> First, it is not known if factorization is an NP-complete problem.Second, there are a great number of NP-complete problems in which
> numbers are not even mentioned. SAT for example. Or various
> graph-theoretic problems.
>
> But yes, if your encoding scheme is stupid enough, every problem can be
> solved in polynomial time. Why is that even remotely interesting?
>
> > So my question is: are there any genuinely "hard" problems that don't
> > depend on (rather arbitrary) choice of number system?
>
> SAT, Hamilton Path, Clique, ...
>
> groente
> -- Sander

I believe your question is as follows, am I correct?

Second, there are a great number of NP-complete problems in which
numbers are
not even mentioned. SAT for example. Or various graph-theoretic
problems. But
yes, if your encoding scheme is stupid enough, every problem can be
solved in
polynomial time. Why is that even remotely interesting? .
First  |  Prev  | 
Pages: 1 2 3 4
Prev: [Port%d] \\.\HCD%d
Next: On The Question of Absolute Undecidability