Jump to content

Talk:Obliq

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Contradictory information about complexity of type-checking

[edit]

The sentence in the intro about type-checking contradicts itself and is generally very confusing:

"A type inference algorithm for record concatenation, subtyping and recursive types has been developed for Obliq, more important it has been proved to be NP-complete[1] and its lowest complexity to be Ο(n3) or if under other modeling up to certain conditions down to Ο(n2)[2] and its best known implementation runs in Ο(n5)."

What does this even mean? It's both NP complete yet the best implementation runs in O(n^5)? Maybe someone can clarify this based on the reference. Cstanford.math (talk) 15:49, 26 February 2020 (UTC)[reply]