I have a weird feeling that finding a single feasible solution to the set cover problem is as hard as SAT problem.
I think that this might be wrong but I am not sure why. To illustrate my thinking, let us look through a toy example of a set cover problem:
$\begin{array}{*{20}{c}} {\min }&{{x_1} + {x_2} + {x_3} + {x_4}}\\ {{\rm{s}}{\rm{.t}}}&{{x_1} + {x_2} + {x_4} \ge 1}\\ {}&{{x_2} + {x_3} + {x_4} \ge 1}\\ {}&{{x_1} + {x_3} + {x_4} \ge 1}\\ {}&{{x_i} \in \left\{ {0,1} \right\}} \end{array}$
The issue of finding the feasible set for this problem could be reformulated as finding an assignment such that the following boolean function $f\left( {{x_1},{x_2},{x_3},{x_4}} \right)$ can be evaluated to true:
$f\left( {{x_1},{x_2},{x_3},{x_4}} \right) = \underbrace {\left( {{x_1} \vee {x_2} \vee {x_4}} \right)}_{{\rm{constraint 1}}} \wedge \underbrace {\left( {{x_2} \vee {x_3} \vee {x_4}} \right)}_{{\rm{constraint 2}}} \wedge \underbrace {\left( {{x_1} \vee {x_3} \vee {x_4}} \right)}_{{\rm{constraint 3}}}$
This really look like a SAT problem for CNF (more like 3-SAT) but finding the assignment such that $f$ is true is very easy by just setting all of the variable $\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ {{x_3}}\\ {{x_4}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} 1\\ 1\\ 1\\ 1 \end{array}} \right]$.
Obviously, this can be done in linear time.
I have another idea is that although finding the feasible solution to the set cover problem looks like SAT. This is a very special instance of SAT with special structure (that I don't know the corresponding terminology to describe) that can be solved quickly.
Could you kindly help me to know where am I wrong ?
Thank you for your enthusiasm
You are correct that the problem of "finding a single feasible solution to minimium set cover" (let's call this problem FS) as you've defined it is possible in linear time. If all we want is a feasible cover, just try all of the sets and see if it forms a cover. This runs in linear time, as you point out. So, this is a decision problem in $P$.
As you point out, there must be an issue in your thinking because SAT is NP-Complete. The issue in your line of thought here is the direction of the "hardness" reduction. If FS is as hard as SAT, then it should be the case that for every instance of SAT, we can define an instance of FS which encodes the SAT problem. You've gone the opposite way: you've demonstrated that FS can always be written as a SAT problem. This only shows that SAT is harder than FS, not that FS is harder than SAT.
For what it's worth: SAT is NP-Complete, which means that every problem contained in NP can be represented as a SAT problem. So it's a good sanity check that you can write FS as a SAT problem! The other way around would grant you fame and riches :)