The STO problem is NP-complete

Krysta, Piotr; Pacholski, Leszek

Local TagsRelease HistoryDetailsSummary

The STO problem is NP-complete

Krysta, P., & Pacholski, L. (1999). The STO problem is NP-complete. Journal of Symbolic Computation, 27(2), 207-219.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3619-C Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-361A-A

Genre: Journal Article

Files

show Files

Locators

show

Creators

show

hide

Creators:
Krysta, Piotr¹, Author
Pacholski, Leszek², Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2Programming Logics, MPI for Informatics, Max Planck Society, ou_40045

Content

show

hide

Free keywords: -

Abstract: We prove that the problem STO of deciding whether or not a finite set $E$ of term equations is subject to occur check is in NP. $E$ is subject to occur check if an execution of the Martelli-Montanari unification algorithm gives for input $E$ a set $E^{\prime} \cup \{ x=t \}$, where $t \not= x$ and $x$ appears in $t$. Apt, van Emde Boas and Welling (1994) proved that STO is NP-hard leaving the problem of NP-completeness open.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02Date issued: 1999

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: Peer

Identifiers: eDoc: 518128
Other: Local-ID: C1256428004B93B8-1CC0C7E2A4CD9515C125688900667F07-Krysta1999a

Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show

hide

Title: Journal of Symbolic Computation

Source Genre: Journal

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 27 (2) Sequence Number: - Start / End Page: 207 - 219 Identifier: -