Can Natural Language Parsing be cubic or linear if it is NP-complete?

Syntactic structure of sentences in a natural language form the base of understanding the notion of the text. Human brain has a parser which can recognise natural languages and is able to resolve ambiguity in sentences. There is computationally no known efficient algorithm which has been devised as yet to model natural language sentences using formal language rules and do probabilistic disambiguation. This causes the problems described in paper by name MPP, MPPWG, MPS and MPS-SCFG to be NP- complete decision problems and are NP-hard.

By parsing natural language, the author means to generate a tree from formal linguistic grammar rules that have leaf nodes as words in the sentence. In line with the topic of the paper, the author wishes to answer the question that is it possible or not to generate an efficient algorithm that gives the probable parse tree which is unambiguous using probabilistic grammar rules. This also points to finding the most plausible structural description of the sentence which is also syntactically correct.

Phrase-structure parsing uses a generative approach of breaking sentences into its constituents while dependency parsing approaches hypothesize word-to-word link which is prominent in many traditional languages as sanskrit, latin or arabic etc. Such parsing techniques can work for simple sentences in polynomial time but could not handle ambiguity. For illustration “The girl plucked the flower with a long stick” has a structural attachment…