...\author

Supported in part by NSF under grant CCR-9424164. Support was also provided by the University of North Carolina at Greensboro in the form of research leave.

...\author

Department of Mathematical Sciences, University of North Carolina at Greensboro, Greensboro, NC 27412, USA. E-mail: wang@uncg.edu.

...

A reduction is called p-length-preserving if it preserves the size of the output within a polynomial of the size of the input. Namely, there is a polynomial such that for all , . Such a length-preserving reduction is also called p-honest in the literature.

...

Note that the index here is selected uniformly as a binary string. How to select , however, is not important to obtain the completeness result. One can use one's favorite distributions to select it, for example, one may select states and transition functions under different distributions.

...

What would be the minimum number of colors that can make the distributional graph edge coloring problem to be complete for DistNP is an interesting issue. It was claimed that 20 colors [VL88], or even much less colors [Ven91], were sufficient. Here we would allow more colors to simplify technical requirements in the completeness proof, which will be presented in Section 6.3. Our main purpose here is to demonstrate that there is a graph problem with a flat distribution that is complete for DistNP.

...

Actually, the distributional graph edge coloring problem stated here is somewhat different from that in [Ven91][VL88]. But the proof technique is essentially the same.

...

An HNN extension of a finitely presented group with stable letters is for words and on such that for each , there is an isomorphism with for every , where, (the subgroup generated by 's), and .

...

We will show in Lemma 6.12 that all these codes are distinct in a.e. and so the input nodes on decreasing order can be uniquely identified from the tournament .

...

If , we consider given by , then is also a linear transformation. The conclusion about implies the same conclusion of .

...

Gurevich [Gur90] (see also [BG95]) showed that the (worst-case) matrix representability problem on unimodular matrices is NP-complete, and he conjectured that the distributional version of the problem is solvable in time polynomial on average. This conjecture has been proven by Cai et. al. [CFKL94]. The reader may find it interesting because it shows that we are working close to the boundary between AP and DistNP [Gur96]. An example in the worst-case complexity with a sharp boundary is 2SAT and 3SAT.