English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently, considerable focus has been given to the problem of determining theboundary between tractable and intractable planning problems. In this paper, westudy the complexity of planning in the class C_n of planning problems,characterized by unary operators and directed path causal graphs. Although thisis one of the simplest forms of causal graphs a planning problem can have, weshow that planning is intractable for C_n (unless P = NP), even if the domainsof state variables have bounded size. In particular, we show that planexistence for C_n^k is NP-hard for k>=5 by reduction from CNFSAT. Here, kdenotes the upper bound on the size of the state variable domains. Our resultreduces the complexity gap for the class C_n^k to cases k=3 and k=4 only, sinceC_n^2 is known to be tractable.

Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard