Intervallum-számítógép
A Wikipédiából, a szabad enciklopédiából
Az intervallum-számítógépek olyan architektúrák, amelyek bitek vagy más egységek helyett intervallumokon dolgoznak. Minden logikai művelet definiálható intervallumokra is. Ezekből más műveletek egyszerűen felépíthetők. Az intervallumok működését a 0 és 1 közé eső alulról zárt intervallumokra írták le. Azaz az intervallumok minden pontja a [0, 1) intervallum része. Azt, hogy egy intervallumba beletartozik-e egy pont, az intervallum karakterisztikus függvénye mondja meg. A fenti leírásból kitűnik, hogy minden intervallumnak potenciálisan végtelen sok pontja van. Azaz az intervallum számítógépek egyszerre végtelen sok logikai értékkel dolgoznak. Ebből következik, hogy számítási erejük jóval nagyobb, mint a hagyományos elvű számítógépeké. Eddig több NP-teljes probléma megoldását leírták az új architektúra segítségével.
[szerkesztés] Intervallum műveletek
[szerkesztés] Megoldható NP teljes problémák
[szerkesztés] Tripartite matching probléma
Nagy Benedek
Tajti Ákos és Nagy Benedek a Tripartite Metching probléma megoldásáról
