arXiv Open Access 2019

Deciding whether a Lattice has an Orthonormal Basis is in co-NP

Christoph Hunkenschröder

Lihat Sumber

Abstrak

We show that the problem of deciding whether a given Euclidean lattice L has an orthonormal basis is in NP and co-NP. Since this is equivalent to saying that L is isomorphic to the standard integer lattice, this problem is a special form of the Lattice Isomorphism Problem, which is known to be in the complexity class SZK.

Topik & Kata Kunci

cs.DM math.CO

Penulis (1)

Christoph Hunkenschröder

Format Sitasi

APA MLA BibTeX

Hunkenschröder, C. (2019). Deciding whether a Lattice has an Orthonormal Basis is in co-NP. https://arxiv.org/abs/1910.03838

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2019
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓