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

[Shuchi Chawla <shuchi@xxxxxxxxxxx>]

I agree with Jin-Yi -- it's the responsibility of the user to make sure the theorem makes sense for the given encoding. Letting information theory be the guide makes sense. In many settings, one can find better encodings than the standard ones, although usually not exponentially better.Â

Here's one example I recently talked about in my class on algorithms for massive datasets. In that context even polynomial improvements in encoding length matter. To encode the shortest paths metric over a graph, you would need to specify the lengths of all |E| edges, or an encoding with O(n^2) "words" for dense graphs. But if the graph is over geometric data, e.g. points in Euclidean space, then there is an O(n) encoding that just specifies the locations of the points, and you compute distances as needed.

Shuchi

On Tue, Nov 14, 2017 at 11:10 AM JIN-YI CAI <jyc@xxxxxxxxxxx> wrote:

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.

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