Enkelt komplext igenkänningsproblem
Det enkla komplexa igenkänningsproblemet är ett beräkningsproblem inom algebraisk topologi . Givet ett förenklat komplex är problemet att avgöra om det är homeomorft till ett annat fast förenklingskomplex. Problemet är oavgörbart för komplex av dimension 5 eller mer.
Bakgrund
Ett abstrakt förenklat komplex (ASC) är en grupp av mängder som är stängd för att ta delmängder (undermängden av en mängd i familjen är också en mängd i familjen). Varje abstrakt förenklat komplex har en unik geometrisk realisering i ett euklidiskt utrymme som ett geometriskt förenklat komplex (GSC), där varje uppsättning med k element i ASC mappas till ett ( k -1)-dimensionellt simplex i GSC. Således ger en ASC en ändlig representation av ett geometriskt objekt. Med tanke på en ASC kan man ställa flera frågor angående topologin för den GSC som den representerar.
Homeomorfism problem
Homeomorphism -problemet är: med tanke på två ändliga enkla komplex som representerar släta grenrör , bestäm om de är homeomorfa .
- Om komplexen är av dimensionen högst 3, är problemet avgörbart. Detta följer av beviset för geometriseringsförmodan .
- För varje d ≥ 4 är homeomorfismproblemet för d -dimensionella förenklade komplex oavgörbart.
Detsamma gäller om "homeomorphic" ersätts med " piecewise-linear homeomorphic ".
Igenkänningsproblem
Igenkänningsproblemet är ett delproblem av homeomorfismproblemet, där ett förenklat komplex ges som en fast parameter . Givet ett annat förenklat komplex som indata, är problemet att avgöra om det är homeomorft till det givna fasta komplexet.
- Igenkänningsproblemet är avgörbart för den 3-dimensionella sfären . Det vill säga, det finns en algoritm som kan avgöra om ett givet förenklat komplex är homeomorft till gränsen för en 4-dimensionell boll.
- Igenkänningsproblemet är obestämbart för den d-dimensionella sfären för alla d ≥ 5. Beviset är genom reduktion till ordet problem för grupper . Av detta kan det bevisas att igenkänningsproblemet är obestämbart för varje fast kompakt d -dimensionell grenrör med d ≥ 5.
- Från och med 2014 är det öppet om igenkänningsproblemet är avgörbart för den 4-dimensionella sfären .
Mångfaldigt problem
Det mångfaldiga problemet är: givet ett ändligt förenklat komplex, är det homeomorft till ett mångfaldigt ? Problemet går inte att avgöra; beviset är genom reduktion från ordet problem för grupper .