# PSPACE and Polynomial reduction

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?

• What have you tried? Can you edit the question and use latex? Jan 31 at 18:59
• 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.
– D.W.
Jan 31 at 20:05
• 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. Jan 31 at 20:07

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.
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.