Re: [theory students] [theory faculty] what is a reasonable encoding?

[JIN-YI CAI <jyc@xxxxxxxxxxx>]

My "ex cathedra" answer is as follows:

The class P and NP are defined for any chosen and fixed alphabet

set \Sigma and (a particular variant of the) TM model.

It does not concern itself with "interpretations" including how to "encode"

objects such as graphs, trees, lists of numbers, ... into strings over \Sigma.

Such matters are concerned with applications.  Whoever invokes

the theory for a particular problem, say in graph theory,

bears the responsibility that encoding such an object to a string in

\Sigma is "reasonable".  This of course includes that it being information

theoretically succinct (no padding), and computationally reasonable (I will

interpret as computable and invertible in P-time.)  But the official

dogma does not get tangled with this. (I say tangled with... because ,

then the question can be what do you mean by computable and

invertible in P-time.... here we are defining P-time...)

This is similar to the situation in axiomatic set theory.

How to use the language

of set theory to deal with "actual" mathematical problems is

the responsibility of the one uses this language of set theory.

This is how axiomatic set theory "resolves" paradoxes such

as "the set of all sets".  It simply does not speak of such things (by

providing no axiom to legitimatize their status as sets), and whoever

invokes such blasphemy bears all the responsibility of inconsistency

(damnation?)

ð

Jin-Yi

---

From: Theory-faculty <theory-faculty-bounces@xxxxxxxxxxx> on behalf of Eric Bach <bach@xxxxxxxxxxx>
Sent: Tuesday, November 14, 2017 9:55:32 AM
To: theory-faculty@xxxxxxxxxxx; theory-students@xxxxxxxxxxx
Subject: [theory faculty] what is a reasonable encoding?

 

I'm about to do NP-completeness in 520.  There is always
the presumption that mathematical objects (sets, graphs,
numbers, ...) are encoded "reasonably".  But what does
that mean?

One way to handle this is to define "standard" encodings,
and then say an encoding is reasonable if there are
poly-time translations (forward and back) to the standard
ones.  But this seems arbitrary, and therefore unsatisfactory.

I'd say that information theory gives a necessary condition
for an encoding to be reasonable.  But that isn't sufficient,
as there might be a really weird (even non-computable) dictionary
between my encoding and the standard one.

Have you ever seen a formal treatment of this question?

Eric
-------------------------------------------------------------------------------
This message was sent to the mailing list for the theory faculty at the
Computer Sciences Department of the University of Wisconsin in Madison.