I was wondering if there is a statement about the spacecomplexity of F and FNP, like P subset of NP subset of PSPACE?

  • $\begingroup$ You can try to prove such a statement yourself. $\endgroup$ – Yuval Filmus May 18 '17 at 14:08
  • $\begingroup$ What are your thoughts? Do you have any conjectures? Have you tried to prove them? Do you understand the proof of "P subset NP subset PSPACE"? Have you tried applying those proof techniques to FP (instead of P) and FNP (instead of NP) to see what happens? Does it work? Is there a specific step where you think that proof approach doesn't work? Folks here can give you better help if you exhaust all possible options on your own and then show us where specifically you got stuck. $\endgroup$ – D.W. May 18 '17 at 15:26
  • $\begingroup$ My thoughts are, that both have to be in PSPACE, because a problem, that can be solved in polynomial time, like in FP, just can use a polynomial space. FNP has to be in PSPACE too, because, according to the definition:"Given an input x and a polynomial-time predicate F(x,y), if there exists a y satisfying F(x,y) then output any such y, otherwise output 'no.'" F(x,y) is a decision problem in P, so i has to be in PSPACE.(Please don't decapitate me if this is blatantly wrong) $\endgroup$ – Illidor May 18 '17 at 15:41
  • $\begingroup$ Can you please confirm, wether this is right or wrong? $\endgroup$ – Illidor May 20 '17 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.