Inverse monoids associated with the complexity class NP

J. C. Birget

doi:10.1007/s00233-018-9990-x

Inverse monoids associated with the complexity class NP

Research output: Contribution to journal › Article › peer-review

Abstract

We study the P versus NP problem through properties of functions and monoids, continuing the work of [3]. Here we consider inverse monoids whose properties and relationships determine whether P is different from NP, or whether injective one-way functions (with respect to worst-case complexity) exist.

Original language	English (US)
Pages (from-to)	369-397
Number of pages	29
Journal	Semigroup Forum
Volume	98
Issue number	2
DOIs	https://doi.org/10.1007/s00233-018-9990-x
State	Published - Apr 15 2019

All Science Journal Classification (ASJC) codes

Algebra and Number Theory

Keywords

Inverse monoids
NP
One-way functions

Access to Document

10.1007/s00233-018-9990-x

Cite this

@article{e78d0e9875cf4be5ad3b8f41cda45e2e,

title = "Inverse monoids associated with the complexity class NP",

abstract = "We study the P versus NP problem through properties of functions and monoids, continuing the work of [3]. Here we consider inverse monoids whose properties and relationships determine whether P is different from NP, or whether injective one-way functions (with respect to worst-case complexity) exist.",

keywords = "Inverse monoids, NP, One-way functions",

author = "Birget, {J. C.}",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2019",

month = apr,

day = "15",

doi = "10.1007/s00233-018-9990-x",

language = "English (US)",

volume = "98",

pages = "369--397",

journal = "Semigroup Forum",

issn = "0037-1912",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Inverse monoids associated with the complexity class NP

AU - Birget, J. C.

PY - 2019/4/15

Y1 - 2019/4/15

N2 - We study the P versus NP problem through properties of functions and monoids, continuing the work of [3]. Here we consider inverse monoids whose properties and relationships determine whether P is different from NP, or whether injective one-way functions (with respect to worst-case complexity) exist.

AB - We study the P versus NP problem through properties of functions and monoids, continuing the work of [3]. Here we consider inverse monoids whose properties and relationships determine whether P is different from NP, or whether injective one-way functions (with respect to worst-case complexity) exist.

KW - Inverse monoids

KW - NP

KW - One-way functions

UR - http://www.scopus.com/inward/record.url?scp=85059523837&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059523837&partnerID=8YFLogxK

U2 - 10.1007/s00233-018-9990-x

DO - 10.1007/s00233-018-9990-x

M3 - Article

AN - SCOPUS:85059523837

SN - 0037-1912

VL - 98

SP - 369

EP - 397

JO - Semigroup Forum

JF - Semigroup Forum

IS - 2

ER -

Inverse monoids associated with the complexity class NP

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this