Search
Author
- Alessio, Meneghetti (1)
- Alex, Pellegrini (1)
- Bingyuan, Hong (1)
- Funing, Li (1)
- next >
Subject
- maximum likelihood dec... (1)
- PMSP (1)
Date issued
Has File(s)
- true (2)
Search Results
The maximum likelihood decoding problem (MLD) is known to be NP-hard and its complexity is strictly related to the security of some post-quantum cryptosystems, that is, the so-called code-based primitives. Analogously, the multivariate quadratic system problem (MQ) is NP-hard and its complexity is necessary for the security of the so-called multivariate-based primitives. In this paper we present a closed formula for a polynomial-time reduction from any instance of MLD to an instance of MQ, and viceversa. We also show a polynomial-time isomorphism between MQ and MLD, thus demonstrating the direct link between the two post-quantum cryptographic families. |
As an essential scheduling problem with several practical applications, the parallel machine scheduling problem (PMSP) with family setups constraints is difficult to solve and proven to be NP-hard. To this end, we present a deep reinforcement learning (DRL) approach to solve a PMSP considering family setups, aiming at minimizing the total tardiness. The PMSP is first modeled as a Markov decision process, where we design a novel variable-length representation of states and actions, so that the DRL agent can calculate a comprehensive priority for each job at each decision time point and then select the next job directly according to these priorities. Meanwhile, the variable-length state matrix and action vector enable the trained agent to solve instances of any scales. To handle the v... |