<p>Yes, because you can just concentrate most of the <span class="math-container">$C$</span> on a small part of the variables, while for rest of the variables can be contained in a single clause each, with a trivial matching. This way you can raise the relative size of the clauses to any polynomial of the remaining variables.</p>

<p>The question would be more interesting if you required the property for all subhypergraphs as well, in which case I suspect the answer to be no.</p>

CC BY-SA 4.0
2020-05-06T11:08:14.747Z
Can we use this restricted version of X3C i.e. |C| < 2q as known NP-complete problem, while proving NP-completeness of other problem? If any reference available for the proof then it will be helpful to me alot...
PAVAN KUMAR
CC BY-SA 4.0
2020-05-06T14:08:52.000Z
I suppose you can. Probably the best reference would be https://cstheory.stackexchange.com/a/46784/419 ;)
domotorp
CC BY-SA 4.0
2020-05-06T06:37:28.617Z
2020-05-06T06:37:28.617Z
domotorp
<p>Exact-Cover-by-3Sets (X3C) is NP-complete.
If the number of classes i.e. |C|&lt;2q then whether this is version of X3C is NP-complete or not?</p>

<cc.complexity-theory>
We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q?
PAVAN KUMAR
# We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q?

(Asked by: username_0 on 2020-05-06)

Exact-Cover-by-3Sets (X3C) is NP-complete.
If the number of classes i.e. |C|<2q then whether this is version of X3C is NP-complete or not?

**Tags:** cc.complexity-theory


---

## 1 answers

### Answer by username_1 on 2020-05-06. Score: 3

Yes, because you can just concentrate most of the $C$ on a small part of the variables, while for rest of the variables can be contained in a single clause each, with a trivial matching. This way you can raise the relative size of the clauses to any polynomial of the remaining variables.

The question would be more interesting if you required the property for all subhypergraphs as well, in which case I suspect the answer to be no.

> **Comments:**
> **username_0**: Can we use this restricted version of X3C i.e. |C| < 2q as known NP-complete problem, while proving NP-completeness of other problem? If any reference available for the proof then it will be helpful to me alot...  
> **username_1**: I suppose you can. Probably the best reference would be https://cstheory.stackexchange.com/a/46784/419 ;)  

---

