Re: [PT] Question on a class of tautologies

Hello Alessio,

I do not fully understand what you mean by "characterize". But the set can 
easily be shown to be coNP-complete:

There is a polytime function f, such that for every formula C of size n, 
we have that f(C) is a formula of shape A->B having the three *-properties

  * all and only the variables in A appear in B;
  * no variable appears twice in A (and so in B);
  * there is no negation in A and in B.

and having size smaller than 2n^2, and such that f(C) is a tautology if 
and only if C is a tautology.

Hope this helps,
Lutz


On Thu, 17 Feb 2011, Alessio Guglielmi wrote:

> Hello,
>
> I would like to receive all sort of information regarding the following 
> problem. If you answer to me exclusively, I'll then summarise to the list 
> after a while.
>
> PROBLEM   Characterise the set of classical propositional tautologies of the 
> form A -> B such that:
>
> * all and only the variables in A appear in B;
> * no variable appears twice in A (and so in B);
> * there is no negation in A and in B.
>
> Cheers,
>
> -Alessio
>