Hiding solutions in model RB: Forced instances are almost as hard as unforced ones

In this paper we study the forced instance spaces of model RB, where one or two arbitrary satisfying assignments have been imposed. We prove rigorously that the expected number of solutions of forced RB instances is asymptotically the same with those of unforced ones. Moreover, the distribution of forced RB instances in the corresponding forced instance space is asymptotically the same with that of unforced RB instances in the unforced instance space. These results imply that the hidden assignments will not lead to easily solvable formulas, and the hardness of solving forced RB instances will be the same with unforced RB instances.

• Publication year

  2021

• Venue

  arXiv.org

• Publication date

  2021-03-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2103.06649
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Finding Hidden Cliques of Size in Nearly Linear Time

  2015cited by this paper
• The solution space structure of random constraint satisfaction problems with growing domains

  2015cited by this paper
• Planting Colourings Silently

  2014cited by this paper
• A general model and thresholds for random constraint satisfaction problems

  2012cited by this paper
• Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains.

  2012cited by this paper
• On the phase transitions of random k-constraint satisfaction problems

  2011cited by this paper
• Finding Hidden Cliques in Linear Time with High Probability

  2010cited by this paper
• Finding Planted Partitions in Random Graphs with General Degree Distributions

  2009cited by this paper
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems

  2009cited by this paper
• Finding hidden cliques in linear time

  2009cited by this paper
• Random constraint satisfaction: Easy generation of hard (satisfiable) instances

  2007influential reference
• The satisfiability threshold for randomly generated binary constraint satisfaction problems

  2006cited by this paper
• Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively

  2005influential reference
• A Simple Model to Generate Hard Satisfiable Instances

  2005cited by this paper
• Consistency and Random Constraint Satisfaction Models with a High Constraint Tightness

  2004cited by this paper
• Many hard examples in exact phase transitions

  2003influential reference
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems

  2001cited by this paper
• Random Constraint Satisfaction: Flaws and Structure

  2001cited by this paper
• Hiding solutions in random satisfiability problems: A statistical mechanics approach

  2001cited by this paper
• Finding and certifying a large hidden clique in a semirandom graph

  2000cited by this paper
• Exact Phase Transitions in Random Constraint Satisfaction Problems

  2000influential reference
• Hiding Cliques for Cryptographic Security

  1998cited by this paper
• Finding a large hidden clique in a random graph

  1998cited by this paper
• Locating the Phase Transition in Binary Constraint Satisfaction Problems

  1996cited by this paper

• No citing papers are available for this paper.