{"id":"W2951745001","doi":"10.48550/arxiv.1211.7161","title":"Unshuffling a Square is NP-Hard","year":2012,"lang":"en","type":"preprint","venue":"arXiv (Cornell University)","topic":"Algorithms and Data Compression","field":"Computer Science","cited_by":2,"is_retracted":false,"has_abstract":true,"ca_institutions":"McMaster University","funders":"","keywords":"String (physics); Square (algebra); Interleaving; Combinatorics; Time complexity; Mathematics; Square tiling; Partition (number theory); Reduction (mathematics); Dynamic programming; Discrete mathematics; Computer science; Algorithm","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.0006574697,0.000903826,0.001372743,0.0005777949,0.001793792,0.003208372,0.00174021,0.001750489,0.008190249],"category_scores_gemma":[0.005305643,0.0006808765,0.001381421,0.00209685,0.002242474,0.005619834,0.00211873,0.003062609,0.002005725],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001449311,"about_ca_system_score_gemma":0.001685946,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003054793,"about_ca_topic_score_gemma":0.004994819,"domain_scores_codex":[0.9984691,0.0002114805,0.0001017332,0.0005638472,0.0003783255,0.0002755006],"domain_scores_gemma":[0.99233,0.006101548,0.000424135,0.0006697278,0.0002964344,0.0001781802],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.001361371,0.000787974,0.004861449,0.002117875,0.0003174298,0.001135311,0.001243424,0.2477394,0.02303952,0.2310761,0.08062215,0.4056981],"study_design_scores_gemma":[0.0001838446,0.0001430657,0.00107313,0.0001064901,0.0000945143,0.0007280484,0.0007165182,0.3125451,0.01677912,0.6436288,0.02393803,0.00006331995],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.3863493,0.002663291,0.5208936,0.01402645,0.0006591802,0.0006607008,0.00768185,0.005677166,0.06138837],"genre_scores_gemma":[0.7392861,0.00116159,0.2240994,0.001894025,0.0003472912,0.0004270911,0.0071106,0.0009984046,0.02467546],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.008190249,"threshold_uncertainty_score":0.02739912,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.1037334628793013,"score_gpt":0.1964665906088665,"score_spread":0.09273312772956512,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}