Consider the following Boolean formula F in Boolean variables x$,$y$\_(1),$y$\_(2)$ :

$($notx$^(^())$y$\_(1))$vv$($x$^(^())$y$\_(2))$

Give a satisfying assignment with x$=0.$

Give a satisfying assignment with x$=1.$

Suppose we are interested in Boolean formulas in Boolean variables

$\{$x$\_(1),$dots,x$\_($m$)\}\backslash$cup $\{$y$\_(1),$dots,y$\_($n$)\}.$

That is$,$ there are m$+$n Boolean variables divided into two groups, with m variables in one

group, and n variables in the other group.

We are interested in knowing whether for any assignment to x$\_(1),$dots,x$\_($m$),$ there exists an

assignment to y$\_(1),$dots,y$\_($n$),$ such that the Boolean formula is satisfiable.

Note that the above example is an instance of this problem, for m$=1,$n$=2,$ satisfying the

requirement above.

Is this problem decidable? If so$,$ give an algorithm and analyse its running time. If not,

prove it$.$