Class complexity P and NP

Asked

Viewed 444 times

5

Good evening, I just started to see FSM (finite state machine) and I read about complexity of algorithms and about P and NP, but I have 2 questions that I don’t understand.

I have this picture of the two machines:

inserir a descrição da imagem aqui

  • What is the complexity of class P?
  • What is the complexity of the class NP?

What would be the complexity of the class?

state-machine
  • 2

    See if the answers to this previous question clarify your doubt.

  • I did some research here too and this other topic you mentioned has already helped a lot!

  • Do you consider that your question is duplicate that, or is there something there that does not explain?

  • @bfavaretto are different.

1 answer

2

John,

Foreplay

Your question is unclear! If it is really "What is the complexity of the P/NP class?" the two displayed automatics are doing nothing -- I assume that’s not what you want.

For the question to make sense you have to define the statement -- complexity to do anything concrete: you have to define / present an algorithm on these automata, it turns out that.

Guessing:

Assuming the two automata will be used to recognize whether a 0/1 string is valid, and looking at the two automata:

  • M1 is a nondeterministic automaton (in state 0 before a "1" I have two possible states to transit.)
  • M2 is the deterministic automaton equivalent to the M1 machine. (probably obtained through a classic nondeterministic automatic conversion algorithm --> deterministic automaton)
  • If M1 has n Stdos, the M2 machine can have a maximum of 2 n states (as is the case here) although I usually have a much smaller number than this.

M2 being a deterministic machine, The algorithm is evident: (transit through each symbol of the input) and the recognizer of this machine is linear relative to the length of the input string (O(k))

The time taken by the M2 recognizer will be more time consuming and will depend on the concrete algorithm used...

Browser other questions tagged state-machine

You are not signed in. Login or sign up in order to post.