-4
$\begingroup$

thanks for your help. This is my first question, so I am very sorry for the bad presentation of the question.

I am studying computer science and this is the question I have been asked for the course of Theory of computation and complexity

Edited question

1.For every two languages $A,B∈PSPACE$, there is a language $C∈PSPACE$ such that $A≤_PC$$B≤_PC$

2.For every two languages $A,B∈PSPACE$ , there is a language $C∈PSPACE$ such that $C≤_PA$$B≤_PC$

3.For every two languages $A,B∈PSPACE$, there is a language $C∈PSPACE$ such that $C≤_PB$$C≤_PA$

What I have tried is:

  1. Correct, we'll take $C∈PSPACE-Complete$ then $C∈PSPACE$ and every $L∈PSPACE$ is $L≤_PC$
    so in particular for languages $A,B∈PSPACE$ there $C≤_PB$$C≤_PA$

  2. Not correct , we'll take $B∈PSPACE-Complete$ then $B∈PSPACE$ , $A∉PSPACE-Complete$ and $A∈PSPACE$. if $C∈PSPACE$ and $C≤_PA$$B≤_PC$, then $C ∈PSPACE-Complete$ and $A ∈PSPACE-Complete$ , Contradiction to the the fact $A∉PSPACE-Complete$!

  3. Not correct , If A or B are trivial then there is no C that $C∈PSPACE$ such that $C≤_PB$$C≤_PA$

Can you please help me determine which of them are correct and which are not (can be several that are correct), and why?

$\endgroup$
3
  • $\begingroup$ What have you tried? Can you edit the question and use latex? $\endgroup$ Jan 31 at 18:59
  • 1
    $\begingroup$ Please ask only one question per post. I see three separate questions here. We are looking for posts that will be useful to others in the future. As such, a post that just contains an exercise-style task and a request for us to solve it for you, or a claim and a request for us to tell you whether it is true or not, is typically not a good fit for our site format. See here for tips on asking questions about exercise-style problems. $\endgroup$
    – D.W.
    Jan 31 at 20:05
  • 1
    $\begingroup$ Although I answered the question, I am downvoting it to discourage "help me" type of questions that show zero effort from the asker side. Also, honestly, I did not thought about answering, but I did after I saw others began answering, which is also not good because if the question stays, and I think I have a more informative answer, then I am kinda forced to answer too. $\endgroup$ Jan 31 at 20:07

2 Answers 2

1
$\begingroup$

Regarding 1: choose $C = \{0x \mid x \in A \} \cup \{1x \mid x\in B\}$.

Regarding $2$: $B \le_P \emptyset \implies B=\emptyset$ however $\{\varepsilon\} \le_P B \implies B \neq \emptyset$.

Regarding $3$: the statement is not well-formed.

$\endgroup$
1
$\begingroup$
  1. Correct: you can choose $C$ to be any $\text{PSPACE-complete}$ language.
  2. The only known counter-examples to this claim are ones where $C$ or $A$ are trivial, and hence, sadly, a counter-example would be one of these boring edge cases (I encourage you to check what happens if you consider $\emptyset$ or $\Sigma^*$). It is worth mentioning however that if $C$ and $A$ are assumed to be nontrivial, then the claim essentially suggests that languages in $\text{PSPACE}$ are in a sense dense w.r.t PTIME reductions, and I believe this was the intention behind the claim. Yet, we don't know whether this is true or false as the claim then is equivalent to $\text{P} = \text{PSPACE}$, which is open.
  3. The claim does not compile.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.